#include <bits/stdc++.h>
using namespace std;
#define ldb double
#define mp make_pair
#define pb push_back
const ldb PI=acos(-1);
const ldb eps=1e-8;
struct pt{ ldb x,y;pt(){}pt(ldb a, ldb b):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);}
bool operator < (pt a, pt b){ return mp(a.x,a.y)<mp(b.x,b.y);}
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 sq(pt a){ return dot(a,a);}
ldb abs(pt a){ return sqrt(sq(a));}
ldb dist(pt a, pt b){ return abs(a-b);}
vector<pt> ConvexHull(vector<pt> a)
{
sort(a.begin(),a.end());
bool ok=1;
for(int i=2;i<a.size();i++) if(cross(a[i+2]-a[i],a[i+1]-a[i])!=0) ok=0;
if(ok) return {a.front(),a.back()};
vector<pt> h;int sz=0;
for(int t=0;t<2;t++)
{
int p=sz+1;
for(int i=0;i<a.size();i++)
{
while(sz>p && cross(a[i]-h[sz-2],h[sz-1]-h[sz-2])>=0) h.pop_back(),sz--;
h.pb(a[i]);sz++;
}
h.pop_back();sz--;
reverse(a.begin(),a.end());
}
return h;
}
ldb Diameter(vector<pt> a)
{
int n=a.size();
auto nxt=[&](int x){ return x==n-1?0:x+1;};
auto pre=[&](int x){ return x==0?n-1:x-1;};
ldb ans=0;
for(int i=0,ptr=0;i<n;i++)
{
while(dist(a[i],a[ptr])<dist(a[i],a[nxt(ptr)])) ptr=nxt(ptr);
while(dist(a[i],a[ptr])<dist(a[i],a[pre(ptr)])) ptr=pre(ptr);
ans=max(ans,dist(a[i],a[ptr]));
}
return ans;
}
pair<bool,pt> Get(pt A, pt B, pt C, ldb r)
{
ldb side=min(dist(A,B),dist(C,B));
A=A-B;A=A/abs(A);
C=C-B;C=C/abs(C);
pt D=A+C;D=D/abs(D);
//printf("A(%f %f) B(%f %f) C(%f %f) D(%f %f)\n",A.x,A.y,B.x,B.y,C.x,C.y,D.x,D.y);
ldb sin_ang=abs(cross(A,D))/abs(A)/abs(D);
ldb cos_ang=dot(A,D)/abs(A)/abs(D);
ldb len=r/sin_ang;
D=D*len;
bool ok=1;
if(r*cos_ang>side) ok=0;
//printf("A(%f %f) B(%f %f) C(%f %f) D(%f %f)\n",A.x,A.y,B.x,B.y,C.x,C.y,D.x,D.y);
return {ok,D+B};
}
vector<pt> a;
ldb dist(pt P, pt a, pt b)
{
pt v=a-b;
ldb c=cross(v,a);
if(dot(v,a)>dot(v,b)) swap(a,b);
if(dot(v,a)<=dot(v,P) && dot(v,P)<=dot(v,b)) return abs((cross(v,P)-c)/abs(v));
return min(dist(P,a),dist(P,b));
}
bool Check(pt P, ldb r)
{
for(int i=1;i<a.size();i++) if(dist(P,a[i-1],a[i])+eps<r) return 0;
if(dist(P,a[0],a.back())+eps<r) return 0;
return 1;
}
bool Check(ldb r)
{
int n=a.size();
auto nxt=[&](int x){ return x==n-1?0:x+1;};
auto pre=[&](int x){ return x==0?n-1:x-1;};
vector<pt> O;
for(int i=0;i<n;i++)
{
auto P=Get(a[pre(i)],a[i],a[nxt(i)],r);
if(P.first && Check(P.second,r)) O.pb(P.second);
}
if(O.size()<2) return 0;
//printf("R: %.3f\n",r);
//for(int i=0;i<n;i++) printf("(%.3f %.3f) ",O[i].x,O[i].y);
//printf("\n");
O=ConvexHull(O);
//printf("Hull:\n");
//for(int i=0;i<n;i++) printf("(%.3f %.3f) ",O[i].x,O[i].y);
//printf("Diam: %.3f\n",Diameter(O));
return Diameter(O)>=2*r;
}
int main()
{
int n,x,y;
scanf("%i",&n);
for(int i=1;i<=n;i++)
{
scanf("%i %i",&x,&y);
a.pb(pt(x,y));
}
ldb top=2e7,bot=0,mid;
while(top-bot>0.001)
{
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 'std::vector<pt> ConvexHull(std::vector<pt>)':
twocircles.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=2;i<a.size();i++) if(cross(a[i+2]-a[i],a[i+1]-a[i])!=0) ok=0;
~^~~~~~~~~
twocircles.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();i++)
~^~~~~~~~~
twocircles.cpp: In function 'bool Check(pt, double)':
twocircles.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<a.size();i++) if(dist(P,a[i-1],a[i])+eps<r) return 0;
~^~~~~~~~~
twocircles.cpp: In function 'int main()':
twocircles.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
twocircles.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&x,&y);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
376 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
1412 ms |
508 KB |
Output isn't correct |
| 6 |
Execution timed out |
4014 ms |
1140 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4027 ms |
984 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4009 ms |
760 KB |
Time limit exceeded |
| 9 |
Execution timed out |
4006 ms |
1240 KB |
Time limit exceeded |
| 10 |
Execution timed out |
4022 ms |
1596 KB |
Time limit exceeded |
