oj.uz

Submission #346626

# Submission time Handle Problem Language Result Execution time Memory
346626 2021-01-10T12:51:48 Z youngyojun 2circles (balkan11_2circles) C++17
100 / 100
 367 ms 10164 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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 15 ms 748 KB Output is correct
6 Correct 82 ms 2060 KB Output is correct
7 Correct 80 ms 2160 KB Output is correct
8 Correct 85 ms 2588 KB Output is correct
9 Correct 213 ms 4844 KB Output is correct
10 Correct 367 ms 10164 KB Output is correct