#include <bits/stdc++.h>
using namespace std;
#define ldb double
struct pt{ldb x,y;pt(ldb a=0,ldb b=0):x(a),y(b){}};
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator * (pt a,ldb b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,ldb b){return pt(a.x/b,a.y/b);}
ldb cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
ldb dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
ldb abs(pt a){return sqrt(dot(a,a));}
ldb dist(pt a,pt b){return abs(a-b);}
pt rot90(pt a){return pt(-a.y,a.x);}
struct line{pt v;ldb c;line(){}line(pt a,pt b):v(b-a),c(cross(v,b)){}};
ldb side(line a,pt b){return a.c-cross(a.v,b);}
ldb offs(line a,pt b){return dot(a.v,b);}
pt sec(line a,line b){return (b.v*a.c-a.v*b.c)/cross(a.v,b.v);}
bool bad(line a,line b,line c){
return offs(b,sec(a,b))>=offs(b,sec(b,c));
}
const int N=50050;
pt p[N],q[N];
int n;
line ln[N];
bool Check(ldb R){
int lo=1,hi=0;
for(int i=1;i<=n;i++){
int j=i==n?1:i+1;
pt D=rot90(p[j]-p[i]);
D=D/abs(D)*R;
line now=line(p[i]+D,p[j]+D);
while(hi>=2&&bad(ln[hi-1],ln[hi],now))hi--;
ln[++hi]=now;
}
while(hi-lo+1>=3){
if(bad(ln[hi-1],ln[hi],ln[lo]))hi--;
else if(bad(ln[hi],ln[lo],ln[lo+1]))lo++;
else break;
}
int m=0;
for(int i=lo;i<=hi;i++){
int j=i==hi?lo:i+1;
q[m++]=sec(ln[i],ln[j]);
}
for(int i=0,j=0;i<m;i++){
while(dist(q[i],q[j])<dist(q[i],q[(j+1)%m]))j=(j+1)%m;
if(dist(q[i],q[j])>=2*R)return 1;
}
return 0;
}
int main(){
scanf("%i",&n);
for(int i=1,x,y;i<=n;i++){
scanf("%i %i",&x,&y);
p[i]=pt(x,y);
}
ldb top=2e7,bot=0,mid;
while(top-bot>1e-3){
mid=(top+bot)/2;
if(Check(mid))bot=mid;
else top=mid;
}
printf("%.3f\n",(top+bot)/2);
return 0;
}
Compilation message
twocircles.cpp: In function 'int main()':
twocircles.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
52 | scanf("%i",&n);
| ~~~~~^~~~~~~~~
twocircles.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
54 | scanf("%i %i",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
3 ms |
3072 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3072 KB |
Output is correct |
| 5 |
Correct |
7 ms |
3072 KB |
Output is correct |
| 6 |
Correct |
27 ms |
3200 KB |
Output is correct |
| 7 |
Correct |
29 ms |
3200 KB |
Output is correct |
| 8 |
Correct |
38 ms |
3328 KB |
Output is correct |
| 9 |
Correct |
71 ms |
3584 KB |
Output is correct |
| 10 |
Correct |
114 ms |
3840 KB |
Output is correct |
