#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
const int MAXN = 5e4;
const ld eps = 1e-8;
int n;
pdd operator*(ld a, pdd b) {
return pdd(b.first*a, b.second*a);
}
pdd operator+(pdd a, pdd b) {
return pdd(a.first+b.first, a.second+b.second);
}
pdd operator-(pdd a, pdd b) {
return pdd(a.first-b.first, a.second-b.second);
}
ld get_mag(pdd v) {
return sqrt(v.first*v.first+v.second*v.second);
}
void normalize(pdd &v) {
ld mag = get_mag(v);
v = (1/mag)*v;
}
class Line {
public:
pdd base;
pdd vec;
ld r_bound;
Line() {}
Line(pdd b, pdd v) {
base = b;
vec = v;
normalize(vec);
}
Line shift(ld dist) { // shifting inwards, 90* from vec direction
pdd start = base;
return Line(base+dist*pdd(-vec.second, vec.first), vec);
}
ld dist_on_line(pdd p) {
if (vec.first < eps) return (p.second-base.second)/vec.second;
return (p.first-base.first)/vec.first;
}
};
ld sin_diff(pdd a, pdd b) {
return b.first*a.second-a.first*b.second;
}
pdd intersect(Line &a, Line &b) {
pdd v3 = b.base-a.base;
ld dist = get_mag(b.base-a.base);
normalize(v3);
dist *= sin_diff(b.vec, v3)/sin_diff(b.vec, a.vec);
return a.base+dist*a.vec;
}
pdd points[MAXN];
pdd tempp[MAXN+5];
Line lines[MAXN];
Line templ[MAXN];
int botpos = -1;
int toppos = -1;
ld max_dist(int num) {
int start = 0;
ld best_mag = 0;
for (int j; j < num; j++) {
ld mag = get_mag(tempp[j]-tempp[0]);
if (mag > best_mag) {
start = j;
best_mag = mag;
}
}
int j = start;
for (int i = 1; i < num; i++) {
ld cur_dist = get_mag(tempp[j%num]-tempp[i]);
ld nxt_dist = get_mag(tempp[(j+1)%num]-tempp[i]);
while (nxt_dist > cur_dist) {
j++;
cur_dist = nxt_dist;
nxt_dist = get_mag(tempp[(j+1)%num]-tempp[i]);
}
best_mag = max(best_mag, cur_dist);
}
return best_mag;
}
ld max_dist() {
ld lbound = -1e9;
ld rbound = 1e9;
for (int i = 0; i < n; i++) {
if (abs(templ[i].vec.first) < eps) {
if (templ[i].vec.second > 0) rbound = templ[i].base.first;
else lbound = templ[i].base.first;
}
}
if (lbound > rbound) return 0;
vector<int> bothull;
vector<int> tophull;
for (int j = botpos; j < botpos+n && templ[j%n].vec.first > eps; j++) {
int i = j%n;
if (bothull.empty()) {
bothull.push_back(i);
continue;
}
ld inter = intersect(templ[bothull.back()], templ[i]).first;
while (bothull.size() > 1 && inter < templ[bothull[bothull.size()-2]].r_bound) {
bothull.pop_back();
inter = intersect(templ[bothull.back()], templ[i]).first;
}
templ[bothull.back()].r_bound = inter;
bothull.push_back(i);
}
for (int j = toppos+n; j > toppos && templ[j%n].vec.first < -eps; j--) {
int i = j%n;
if (tophull.empty()) {
tophull.push_back(i);
continue;
}
ld inter = intersect(templ[tophull.back()], templ[i]).first;
while (tophull.size() > 1 && inter < templ[tophull[tophull.size()-2]].r_bound) {
tophull.pop_back();
inter = intersect(templ[tophull.back()], templ[i]).first;
}
templ[tophull.back()].r_bound = inter;
tophull.push_back(i);
}
int bstart = 0;
int tstart = 0;
int bend = bothull.size()-1;
int tend = tophull.size()-1;
while (bstart+1 < bothull.size() && templ[bothull[bstart]].r_bound < lbound) bstart++;
while (tstart+1 < tophull.size() && templ[tophull[tstart]].r_bound < lbound) tstart++;
while (bend > 0 && templ[bothull[bend-1]].r_bound > rbound) bend--;
while (tend > 0 && templ[tophull[tend-1]].r_bound > rbound) tend--;
if (abs(templ[tophull[tstart]].vec.second) > eps || abs(templ[bothull[bstart]].vec.second) > eps)
lbound = max(lbound, intersect(templ[tophull[tstart]], templ[bothull[bstart]]).first);
if (abs(templ[tophull[tend]].vec.second) > eps || abs(templ[bothull[bend]].vec.second) > eps)
rbound = min(rbound, intersect(templ[tophull[tend]], templ[bothull[bend]]).first);
int num = 0;
Line lb(pdd(lbound, 0), pdd(0, -1));
Line rb(pdd(rbound, 0), pdd(0, 1));
for (int i = bstart; i < bend; i++) tempp[num++] = intersect(templ[bothull[i]], templ[bothull[i+1]]);
tempp[num++] = intersect(templ[bothull[bend]], rb);
tempp[num++] = intersect(templ[tophull[tend]], rb);
for (int i = tend-1; i >= tstart; i--) tempp[num++] = intersect(templ[tophull[i]], templ[tophull[i+1]]);
tempp[num++] = intersect(templ[tophull[tstart]], lb);
tempp[num++] = intersect(templ[bothull[bstart]], lb);
return max_dist(num);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> points[i].first >> points[i].second;
}
for (int i = 0; i < n; i++) {
lines[i] = Line(points[i], points[(i+1)%n]-points[i]);
if (lines[i].vec.first > eps && lines[(i+n-1)%n].vec.first < eps) botpos = i;
if (lines[i].vec.first < -eps && lines[(i+1)%n].vec.first > -eps) toppos = i;
}
ld mn = 0;
ld mx = 6e6;
int iters = 40;
for (int t = 0; t < iters; t++) {
ld dist = (mn+mx)/2;
for (int i = 0; i < n; i++) templ[i] = lines[i].shift(dist);
if (max_dist() > 2*dist) mn = dist;
else mx = dist;
}
cout << setprecision(20) << mn << "\n";
}
Compilation message
twocircles.cpp: In member function 'Line Line::shift(ld)':
twocircles.cpp:46:7: warning: variable 'start' set but not used [-Wunused-but-set-variable]
46 | pdd start = base;
| ^~~~~
twocircles.cpp: In function 'ld max_dist()':
twocircles.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | while (bstart+1 < bothull.size() && templ[bothull[bstart]].r_bound < lbound) bstart++;
| ~~~~~~~~~^~~~~~~~~~~~~~~~
twocircles.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | while (tstart+1 < tophull.size() && templ[tophull[tstart]].r_bound < lbound) tstart++;
| ~~~~~~~~~^~~~~~~~~~~~~~~~
twocircles.cpp: In function 'ld max_dist(int)':
twocircles.cpp:77:11: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
77 | for (int j; j < num; j++) {
| ^
twocircles.cpp: In function 'int main()':
twocircles.cpp:34:7: warning: '<anonymous>.Line::r_bound' may be used uninitialized in this function [-Wmaybe-uninitialized]
34 | class Line {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8148 KB |
Output isn't correct |
| 2 |
Incorrect |
7 ms |
8052 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
8148 KB |
Output isn't correct |
| 4 |
Incorrect |
8 ms |
8156 KB |
Output isn't correct |
| 5 |
Incorrect |
18 ms |
8268 KB |
Output isn't correct |
| 6 |
Incorrect |
52 ms |
8620 KB |
Output isn't correct |
| 7 |
Incorrect |
60 ms |
8868 KB |
Output isn't correct |
| 8 |
Incorrect |
87 ms |
9432 KB |
Output isn't correct |
| 9 |
Incorrect |
166 ms |
10592 KB |
Output isn't correct |
| 10 |
Incorrect |
241 ms |
11188 KB |
Output isn't correct |
