#include<stdio.h>
#include<math.h>
#define PI 3.14159
struct point{
double x, y;
}w[100100], Deq[50100];
double S;
int n;
bool ccw(point p, point q, point r){
return (q.x - p.x)*(r.y - p.y) - (q.y - p.y)*(r.x - p.x) > 0;
}
point inter(point a, point b, point c, point d){
double t = (-(a.y - b.y)*(d.x - b.x) + (a.x - b.x)*(d.y - b.y)) / ((a.y - b.y)*(c.x - d.x) - (a.x - b.x)*(c.y - d.y));
point R;
R.x = t*c.x + (1 - t)*d.x;
R.y = t*c.y + (1 - t)*d.y;
return R;
}
double dis(point a, point b){
return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);
}
bool IsPossible(double R){
int i, h = 1, t = 0, ck = 0, pv;
double dx, dy, L;
point P1, P2;
for (i = 0; i < n; i++){
dx = -(w[i + 1].y - w[i].y);
dy = w[i + 1].x - w[i].x;
L = sqrt(dx*dx + dy*dy);
dx = dx*R / L, dy = dy*R / L;
P1.x = w[i].x + dx + (w[i].x - w[i + 1].x)*1e5, P1.y = w[i].y + dy + (w[i].y - w[i + 1].y)*1e5;
P2.x = w[i + 1].x + dx + (w[i + 1].x - w[i].x)*1e5, P2.y = w[i + 1].y + dy + (w[i + 1].y - w[i].y)*1e5;
if (i == 0){
Deq[++t] = P1, Deq[++t] = P2;
continue;
}
if (!ccw(P1, P2, Deq[t])){
while (h <= t && !ccw(P1, P2, Deq[t]))t--;
if (h > t)return false;
Deq[t + 1] = inter(Deq[t], Deq[t + 1], P1, P2);
t++;
}
if (!ccw(P1, P2, Deq[h])){
while (h <= t && !ccw(P1, P2, Deq[h]))h++;
Deq[h - 1] = inter(Deq[h - 1], Deq[h], P1, P2);
h--;
Deq[++t] = Deq[h];
}
else Deq[++t] = P2;
}
pv = h + 1;
for (i = h; i < t; i++){
while (dis(Deq[i], Deq[pv])<dis(Deq[i], Deq[pv + 1])){
pv++;
if (pv == t)pv = h;
}
if (sqrt(dis(Deq[i], Deq[pv])) >= 2*R)return true;
}
return false;
}
int main()
{
int i;
double B, E, R;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%lf%lf", &w[i].x, &w[i].y);
w[n] = w[0];
for (i = 0; i < n; i++)
S += w[i].x*w[i + 1].y - w[i].y*w[i + 1].x;
if (S < 0)S = -S;
S /= 2;
B = 0, E = sqrt(S / (2 * PI));
while (E-B > 0.0001){
R = (B + E)*0.5;
if (IsPossible(R))B = R;
else E = R;
}
printf("%.3lf\n", R);
}
Compilation message
2circles.cpp: In function 'bool IsPossible(double)':
2circles.cpp:23:23: warning: unused variable 'ck' [-Wunused-variable]
int i, h = 1, t = 0, ck = 0, pv;
^
2circles.cpp: In function 'int main()':
2circles.cpp:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
2circles.cpp:67:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lf%lf", &w[i].x, &w[i].y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3476 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3476 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3476 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3476 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3476 KB |
Output is correct |
| 6 |
Correct |
19 ms |
3476 KB |
Output is correct |
| 7 |
Correct |
23 ms |
3476 KB |
Output is correct |
| 8 |
Correct |
23 ms |
3476 KB |
Output is correct |
| 9 |
Correct |
63 ms |
3476 KB |
Output is correct |
| 10 |
Correct |
99 ms |
3476 KB |
Output is correct |
