Submission #157408

#	Time	Username	Problem	Language	Result	Execution time	Memory
157408		youngyojun	2circles (balkan11_2circles)	C++11	100 / 100	348 ms	9996 KiB

twocircles

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[sz(V)-2])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define upmax(a,b) (a)=max((a),(b))
using namespace std;
typedef long double ld;
typedef pair<ld, ld> pdd;
const ld EPS = 1e-6;
pdd operator + (pdd a, pdd b) { return pdd(a.fi+b.fi, a.se+b.se); }
pdd operator - (pdd a, pdd b) { return pdd(a.fi-b.fi, a.se-b.se); }
ld operator * (pdd a, pdd b) { return a.fi*b.se - a.se*b.fi; }
ld operator / (pdd a, pdd b) { return a.fi*b.fi + a.se*b.se; }
pdd operator * (pdd a, ld b) { return pdd(a.fi*b, a.se*b); }
ld ccw(pdd a, pdd b, pdd c) { return a*b + b*c + c*a; }
ld norm(pdd p) { return sqrt(p/p); }
ld getDist(pdd a, pdd b) { return norm(a-b); }
pdd rot(pdd p) { return pdd(-p.se, p.fi); }
pdd sect(pdd p1, pdd d1, pdd p2, pdd d2) {
	pdd n1 = rot(d1);
	ld k = (p1-p2)/n1 / (d2/n1);
	return p2 + d2*k;
}

const int MAXN = 50005;

struct LNE {
	LNE(pdd p, pdd d)
		: p(p), d(d), n(rot(d)) {}
	pdd p, d, n;
};
pdd sect(LNE &a, LNE &b) { return sect(a.p, a.d, b.p, b.d); }

pdd P[MAXN];

int N;

bool valid(LNE &a, LNE &b, LNE &c) {
	return (sect(b, c) - a.p) / a.n > -EPS;
}

bool isp(ld X) {
	deque<LNE> T;
	for(int i = 0; i < N; i++) {
		pdd d = P[i+1]-P[i], n = rot(d);
		pdd p = P[i] + n * (X / norm(n));
		LNE lne(p, d);
		for(; 1 < sz(T) && !valid(befv(T), T.back(), lne); T.pop_back());
		T.eb(lne);
	}
	for(; 2 < sz(T) && !valid(befv(T), T.back(), T[0]); T.pop_back());
	for(; 2 < sz(T) && !valid(T.back(), T[0], T[1]); T.pop_front());
	if(sz(T) < 3) return false;

	vector<pdd> V; int n = sz(T);
	for(int i = 0; i < n; i++) V.eb(sect(T[i], T[(i+1)%n]));

	ld ret = 0;
	for(int i = 0, j = 1; i < n; j %= n) {
		upmax(ret, getDist(V[i], V[j]));
		((V[(i+1)%n]-V[i]) * (V[(j+1)%n]-V[j]) > 0 ? j : i)++;
	}

	return ret >= X*2;
}

ld getAns() {
	ld s = 0, e = (max_element(P, P+N)->fi - min_element(P, P+N)->fi) / 2;
	for(int t = 40; t--;) {
		ld m = (s+e) / 2;
		(isp(m) ? s : e) = m;
	}
	return (s+e) / 2;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	for(int i = 0; i < N; i++) cin >> P[i].first >> P[i].second;
	P[N] = P[0];

	printf("%.10Lf\n", getAns());
	return 0;
}

• Subtask 1: 100 / 100