#include <bits/stdc++.h>
using namespace std;
typedef double T;
struct pt {
T x,y;
pt(T x=0, T y=0): x(x), y(y) {}
pt operator+(pt p) { return {x+p.x, y+p.y}; }
pt operator-(pt p) { return {x-p.x, y-p.y}; }
pt operator*(T d) { return {x*d, y*d}; }
pt operator/(T d) { return {x/d, y/d}; }
};
bool operator==(pt a,pt b){return a.x==b.x&&a.y==b.y;}
bool operator!=(pt a, pt b) { return !(a == b); }
ostream& operator<<(ostream& os, pt p) {
return os << "("<< p.x << "," << p.y << ")";
}
T sq(pt p) { return p.x*p.x + p.y*p.y; }
double abs(pt p) { return sqrt(sq(p)); }
T dot(pt v, pt w) { return v.x*w.x + v.y*w.y; }
T cross(pt v, pt w) { return v.x*w.y - v.y*w.x; }
template <typename T> int sgn(T x) {
return (T(0) < x) - (x < T(0));
}
const double eps = 1e-9;
struct line {
pt v; T c;
// from direction vector v and offset c
line(pt v, T c) : v(v), c(c) {}
// from equation ax+by=c
line(T a, T b, T c) : v({b,-a}), c(c) {}
// from points P and Q
line(pt p, pt q) : v(q-p), c(cross(v,p)) {}
T side(pt p) { return cross(v,p)-c; }
};
// intersection of two lines
bool inter(line l1, line l2, pt &out) {
T d = cross(l1.v, l2.v);
if(d == 0) return false;
out = (l2.v*l1.c - l1.v*l2.c) / d;
return true;
}
struct hp_t {
pt p1, p2;
double a;
hp_t() { }
hp_t(pt tp1, pt tp2) : p1(tp1), p2(tp2) {
tp2 = tp2 - tp1;
a = atan2(tp2.y, tp2.x);
}
bool operator==(const hp_t &r) const {
return fabs(a - r.a) < eps;
}
bool operator<(hp_t &r) {
if(fabs(a - r.a) < eps)
return cross(r.p2 - r.p1, p2 - r.p1) >= -eps;
else return a < r.a;
}
} hp[50010];
int cnt;
void addhp(pt p1, pt p2) {
// cout << p1.x << " " << p1.y << " to " << p2.x << " " << p2.y << endl;
hp[++cnt] = hp_t(p1, p2);
}
double maxd = 1e8;
void init() {
cnt = 0;
addhp(pt(-maxd, -maxd), pt(maxd, -maxd));
addhp(pt(maxd, -maxd), pt(maxd, maxd));
addhp(pt(maxd, maxd), pt(-maxd, maxd));
addhp(pt(-maxd, maxd), pt(-maxd, -maxd));
}
bool checkhp(hp_t h1, hp_t h2, hp_t h3) {
pt p;
inter(line(h1.p1, h1.p2), line(h2.p1, h2.p2), p);
return cross(p - h3.p1, h3.p2 - h3.p1) > eps;
}
vector<pt> ishp() {
sort(hp + 1, hp + 1 + cnt);
cnt = unique(hp + 1, hp + 1 + cnt) - hp - 1;
deque<hp_t> dq;
dq.push_back(hp[1]);
dq.push_back(hp[2]);
for (int i = 3; i <= cnt; ++i) {
while (dq.size() > 1 && checkhp(*----dq.end(),
*--dq.end(), hp[i])) dq.pop_back();
while (dq.size() > 1 && checkhp(*++dq.begin(),
*dq.begin(), hp[i])) dq.pop_front();
dq.push_back(hp[i]);
}
while (dq.size() > 1 && checkhp(*----dq.end(),
*--dq.end(), dq.front())) dq.pop_back();
while (dq.size() > 1 && checkhp(*++dq.begin(),
*dq.begin(), dq.back())) dq.pop_front();
dq.push_front(dq.back());
vector<pt> res;
while (dq.size() > 1) {
hp_t tmp = dq.front();
dq.pop_front();
pt I;
inter(line(tmp.p1, tmp.p2),
line(dq.front().p1, dq.front().p2), I);
res.push_back(I);
}
return res;
}
int n;
pt v[50010];
pt orthogonal(pt a, double len) {
double x = -a.y;
double y = a.x;
double mag = sqrt(x*x + y*y);
return pt(x * (len / mag), y * (len / mag));
}
double diameter(vector <pt> v) {
auto dist = [&] (pt a, pt b) {
return dot(a - b, a - b);
};
double ans = 0;
int k = v.size();
for(int i = 0; i < k; i++) {
int l = 0, r = k - 1;
while(l < r) {
int m = (l + r) >> 1;
if(dist(v[i], v[(i + m) % k]) <= dist(v[i], v[(i + m + 1) % k])) {
l = m + 1;
} else {
r = m;
}
}
ans = max(ans, dist(v[i], v[l]));
}
return sqrt(ans) / 2;
}
bool good(double g) {
cnt = 0;
init();
for(int i = 0; i < n; i++) {
pt shift = orthogonal(v[(i + 1) % n] - v[i], g);
addhp(v[i] + shift, v[(i + 1) % n] + shift);
// cout << shift.x << ' ' << shift.y << endl;
}
vector <pt> p = ishp();
return diameter(p) >= g;
}
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> v[i].x >> v[i].y;
}
double l = 0, r = 3e7;
for(int i = 0; i < 100; i++) {
double m = (l + r) * 0.5;
if(good(m)) l = m;
else r = m;
}
cout << setprecision(3) << fixed << l << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
9 ms |
3072 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
3072 KB |
Output isn't correct |
| 5 |
Correct |
62 ms |
3200 KB |
Output is correct |
| 6 |
Incorrect |
343 ms |
3812 KB |
Output isn't correct |
| 7 |
Incorrect |
316 ms |
3840 KB |
Output isn't correct |
| 8 |
Correct |
410 ms |
3796 KB |
Output is correct |
| 9 |
Correct |
921 ms |
4652 KB |
Output is correct |
| 10 |
Incorrect |
1510 ms |
5772 KB |
Output isn't correct |
