#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 = 0; 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-1;
ld rbound = 1e9+1;
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 (lbound < -1e9)
lbound = intersect(templ[tophull[tstart]], templ[bothull[bstart]]).first;
if (rbound > 1e9)
rbound = intersect(templ[tophull[tend]], templ[bothull[bend]]).first;
if (lbound > rbound) return 0;
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 = 500;
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 '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 |
Correct |
7 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
8052 KB |
Output isn't correct |
| 3 |
Incorrect |
19 ms |
8184 KB |
Output isn't correct |
| 4 |
Incorrect |
16 ms |
8184 KB |
Output isn't correct |
| 5 |
Incorrect |
149 ms |
8276 KB |
Output isn't correct |
| 6 |
Incorrect |
685 ms |
8908 KB |
Output isn't correct |
| 7 |
Incorrect |
629 ms |
8680 KB |
Output isn't correct |
| 8 |
Incorrect |
960 ms |
9172 KB |
Output isn't correct |
| 9 |
Incorrect |
1963 ms |
10068 KB |
Output isn't correct |
| 10 |
Incorrect |
2879 ms |
10400 KB |
Output isn't correct |
