#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 && !isIncluded(ln[i], getIntersect(dq[dq.size()-2], dq.back())))
dq.pop_back();
while(dq.size() >= 2 && !isIncluded(ln[i], getIntersect(dq[0], dq[1])))
dq.pop_front();
if(dq.size() < 2 || isIncluded(dq[0], getIntersect(dq.back(), ln[i])))
dq.push_back(ln[i]);
}
vector<point> res;
if(dq.size() >= 3) for(int i=0; i<dq.size(); i++)
res.push_back(getIntersect(dq[i], dq[(i+1)%dq.size()]));
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;
}
Compilation message
twocircles.cpp: In function 'std::vector<point> HPI(std::vector<Line>&)':
twocircles.cpp:45:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(dq.size() >= 3) for(int i=0; i<dq.size(); i++)
~^~~~~~~~~~
twocircles.cpp: In function 'int main()':
twocircles.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
twocircles.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
twocircles.cpp: In function 'double calipers(std::vector<point>&)':
twocircles.cpp:59:3: warning: 'rm' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(i1 == rm) i2 = (i2 + 1) % SZ(ch);
^~
twocircles.cpp:60:8: warning: 'lm' may be used uninitialized in this function [-Wmaybe-uninitialized]
else if(i2 == lm) i1 = (i1 + 1) % SZ(ch);
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
4 ms |
376 KB |
Output is correct |
| 4 |
Correct |
4 ms |
376 KB |
Output is correct |
| 5 |
Correct |
26 ms |
644 KB |
Output is correct |
| 6 |
Correct |
178 ms |
1656 KB |
Output is correct |
| 7 |
Correct |
171 ms |
1704 KB |
Output is correct |
| 8 |
Correct |
178 ms |
1656 KB |
Output is correct |
| 9 |
Correct |
454 ms |
3384 KB |
Output is correct |
| 10 |
Correct |
761 ms |
5732 KB |
Output is correct |
