| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 153695 | junodeveloper | 2circles (balkan11_2circles) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#define SZ(x) ((int)x.size())
using namespace std;
struct point {
double x, y;
point() {}
point(double x, double y) : x(x), y(y) {}
bool operator<(const point& b) const {
return x == b.x ? y < b.y : x < b.x;
}
};
struct Line {
point s, t;
Line() {}
Line(point s, point t) : s(s), t(t) {}
};
double cross(point& a, point& b, point& c) {
return (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y);
}
double dirCross(Line& a, Line& b) {
return (a.t.y - a.s.y) * (b.t.x - b.s.x) - (b.t.y - b.s.y) * (a.t.x - a.s.x);
}
point getIntersect(Line& a, Line& b) {
double det = dirCross(a, b);
double dx = b.s.x - a.s.x;
double dy = b.s.y - a.s.y;
double v = (-(b.t.y - b.s.y) * dx + (b.t.x - b.s.x) * dy) / det;
return point(a.s.x + v * (a.t.x - a.s.x), a.s.y + v * (a.t.y - a.s.y));
}
bool isIncluded(Line& ln, point p) {
return cross(ln.s, ln.t, p) >= 0;
}
vector<point> HPI(vector<line>& ln) {
deque<line> dq;
for(int i=0; i<sz(ln); i++) {
while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), ln[i]))
dq.pop_back();
while(dq.size() >= 2 && bad(dq[0], dq[1], ln[i]))
dq.pop_front();
if(dq.size() < 2 || !bad(dq.back(), ln[i], dq[0]))
dq.push_back(ln[i]);
}
vector<point> res;
if(dq.size() >= 3) for(int i=0; i<sz(dq); i++) {
int j=(i+1)%sz(dq);
point v;
if(!line_intersect(dq[i].s, dq[i].t, dq[j].s, dq[j].t, v)) continue;
res.push_back(v);
}
return res;
}
double calipers(vector<point>& ch) {
double mn = 9e18, mx = -9e18, res = 0;
int lm, rm;
for(int i=0; i<SZ(ch); i++) {
if(mn > ch[i].x) mn = ch[i].x, lm = i;
if(mx < ch[i].x) mx = ch[i].x, rm = i;
}
int i1 = lm, i2 = rm;
while(i1 != rm || i2 != lm) {
res = max(res, hypot(ch[i1].x - ch[i2].x, ch[i1].y - ch[i2].y));
if(i1 == rm) i2 = (i2 + 1) % SZ(ch);
else if(i2 == lm) i1 = (i1 + 1) % SZ(ch);
else {
int ni1 = (i1 + 1) % SZ(ch);
int ni2 = (i2 + 1) % SZ(ch);
if((ch[ni1].y - ch[i1].y) * (ch[ni2].x - ch[i2].x) >
(ch[ni2].y - ch[i2].y) * (ch[ni1].x - ch[i1].x))
i1 = ni1;
else i2 = ni2;
}
}
return res;
}
int main() {
int n;
vector<point> p;
scanf("%d", &n);
for(int i=0,x,y; i<n; i++) {
scanf("%d%d", &x, &y);
p.push_back(point(x, y));
}
double lo = 0, hi = 1e9;
for(int tt=0; tt<100; tt++) {
double mid = (lo + hi) / 2;
vector<Line> ln;
for(int i=0; i<n; i++) {
double dx = -(p[(i+1)%n].y - p[i].y);
double dy = p[(i+1)%n].x - p[i].x;
double sz = hypot(dx, dy);
dx = dx / sz * mid, dy = dy / sz * mid;
ln.push_back(Line(point(p[i].x + dx, p[i].y + dy),
point(p[(i+1)%n].x + dx, p[(i+1)%n].y + dy)));
}
vector<point> ch = HPI(ln);
if(ch.size() >= 3) {
double d = calipers(ch);
if(d >= mid * 2) lo = mid;
else hi = mid;
} else hi = mid;
}
printf("%.3f", lo);
return 0;
}