답안 #957497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957497 2024-04-03T21:48:08 Z kobor 두 개의 원 (balkan11_2circles) C++17
100 / 100
598 ms 6540 KB
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	using P = Point;
	T x, y;
	explicit Point(T _x=0, T _y=0) : x(_x), y(_y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

template<class P>
pair<int, P> lineInter(P s1, P e1, P s2, P e2) {
	auto d = (e1 - s1).cross(e2 - s2);
	if (d == 0) // if parallel
		return {-(s1.cross(e1, s2) == 0), P(0, 0)};
	auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
	return {1, (s1 * p + e1 * q) / d};
}

using P = Point<double>;
int hf(P a) { return a.y < 0 || (a.y == 0 && a.x < 0); }

struct polarCmp {
	bool operator()(const P &a, const P &b) const {
		return hf(a) == hf(b) ? a.cross(b) > 0 : hf(a) < hf(b);
	}
};

struct HalfplaneSet : map<P, P, polarCmp> {
	double INF = 1e8, area = 8 * INF * INF;

	HalfplaneSet() {
		P p(-INF, -INF), d(1, 0);
		FOR(k, 0, 4) {
			insert({d, p});
			p = p + d * 2 * INF;
			d = d.perp();
		}
	}

	auto fix(auto it) { return it == end() ? begin() : it; }
	auto getNext(auto it) { return fix(next(it)); }
	auto getPrev(auto it) {
		return it == begin() ? prev(end()) : prev(it);
	}

	auto uSide(auto it, int change) {	// 1 - add, -1 - del
		area += change * it->nd.cross(getNext(it)->nd);
	}

	auto del(auto it) {
		uSide(getPrev(it), -1), uSide(it, -1);
		it = fix(erase(it));
		if(size()) uSide(getPrev(it), 1);
		return it;
	}

	void add(P s, P e) {
		deb(s, e);
		auto eval = [&](auto it) { 
			return sgn(s.cross(e, it->nd));
		};
		auto intersect = [&](auto it) {
			return lineInter(s, e, it->nd, it->st + it->nd).nd;
		};

		auto it = fix(lower_bound(e - s));
		if(empty() || eval(it) >= 0) return;
		while(size() && eval(getPrev(it)) < 0) del(getPrev(it));
		while(size() && eval(getNext(it)) < 0) it = del(it);
		if(empty()) return;
		if(eval(getNext(it)) > 0) {
			uSide(getPrev(it), -1), uSide(it, -1);
			it->nd = intersect(it);
			uSide(getPrev(it), 1), uSide(it, 1);
		}
		else it = del(it);
		it = getPrev(it);
		uSide(it, -1);
		insert(it, {e - s, intersect(it)});
		uSide(it, 1), uSide(getNext(it), 1);
		if(eval(it) == 0) del(it);
	}

	double maxDot(P a) {
		return a.dot(fix(lower_bound(a.perp()))->nd);
	}

	double getArea() { return area / 2; }
};

void solve() {
	int n;
	cin >> n;
	vector<P> pts;
	FOR(i, 0, n) {
		int x, y;
		cin >> x >> y;
		pts.pb(P(x, y));
	}
	auto check = [&](double r) {
		HalfplaneSet jan;
		FOR(i, 0, n) {
			P s = pts[i], e = pts[(i + 1) % n];
			P d = (e - s).normal() * r;
			jan.add(s + d, e + d);
		}
		vector<P> cnd;
		for(auto &[_, pt]: jan) cnd.pb(pt);
		if(SZ(cnd) == 0) return false;
		double best = 0;
		int j = 1 % SZ(cnd);
		FOR(i, 0, SZ(cnd)) {
			P a = cnd[i], b = cnd[(i + 1) % SZ(cnd)];
			while(a.cross(b, cnd[j]) < a.cross(b, cnd[(j + 1) % SZ(cnd)])) j = (j + 1) % SZ(cnd);
			for(P cand: {a, b}) best = max(best, (cand - cnd[j]).dist());
		}
		return best >= r * 2;
	};
	double l = 0, r = 1e8;
	FOR(it, 0, 60) {
		double mid = (l + r) / 2;
		(check(mid) ? l : r) = mid;
	}
	cout << fixed << setprecision(9);
	cout << l << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	// cin >> tt;
	FOR(te, 0, tt) solve();
	return 0;
}

Compilation message

twocircles.cpp:18:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
twocircles.cpp:18:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
twocircles.cpp:18:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
twocircles.cpp:20:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
twocircles.cpp:20:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~
twocircles.cpp:89:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   89 |  auto fix(auto it) { return it == end() ? begin() : it; }
      |           ^~~~
twocircles.cpp:90:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   90 |  auto getNext(auto it) { return fix(next(it)); }
      |               ^~~~
twocircles.cpp:91:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   91 |  auto getPrev(auto it) {
      |               ^~~~
twocircles.cpp:95:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   95 |  auto uSide(auto it, int change) { // 1 - add, -1 - del
      |             ^~~~
twocircles.cpp:99:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   99 |  auto del(auto it) {
      |           ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 28 ms 600 KB Output is correct
6 Correct 138 ms 1944 KB Output is correct
7 Correct 158 ms 988 KB Output is correct
8 Correct 244 ms 2016 KB Output is correct
9 Correct 386 ms 4060 KB Output is correct
10 Correct 598 ms 6540 KB Output is correct