oj.uz

Submission #157408

# Submission time Handle Problem Language Result Execution time Memory
157408 2019-10-11T11:53:21 Z youngyojun 2circles (balkan11_2circles) C++11
100 / 100
 348 ms 9996 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 14 ms 772 KB Output is correct
6 Correct 85 ms 2160 KB Output is correct
7 Correct 60 ms 2128 KB Output is correct
8 Correct 92 ms 2568 KB Output is correct
9 Correct 198 ms 4748 KB Output is correct
10 Correct 348 ms 9996 KB Output is correct