#include<bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
const double PI=3.1415926535897932384626433832795;
typedef pair<double,double> pt;
int ccw(pt a, pt b, pt c) {
b.xx-=a.xx;c.xx-=a.xx;
b.yy-=a.yy;c.yy-=a.yy;
if(b.yy*c.xx < c.yy*b.xx) {
return -1;
}else if(b.yy*c.xx == c.yy*b.xx) {
return 0;
}
return 1;
}
double len(pt a) {
return sqrt(a.xx*a.xx+a.yy*a.yy);
}
double dist(pt& a, pt& b) {
return len({a.xx-b.xx, a.yy-b.yy});
}
pt egyseg(pt& a) {
double l=len(a);
return {a.xx/l, a.yy/l};
}
double angle(pt a, pt b, pt c) {
a.xx-=b.xx;c.xx-=b.xx;
a.yy-=b.yy;c.yy-=b.yy;
return acos((a.xx*c.xx+a.yy*c.yy)/(len(a)*len(c)));
}
double diameter(vector<pt> &poly) {
double ans=0.0;
for(int i=0;i<(int)poly.size();++i) {
for(int j=0;j<(int)poly.size();++j) {
ans=max(ans, dist(poly[i], poly[j]));
}
}
return ans;
}
bool intersect(pair<pt,pt> sz1, pair<pt,pt> sz2) {
if(ccw(sz1.xx, sz1.yy, sz2.xx)==ccw(sz1.xx, sz1.yy, sz2.yy)) return false;
if(ccw(sz2.xx, sz1.xx, sz1.yy)<0) swap(sz1.xx, sz1.yy);
return ccw(sz2.xx, sz1.xx, sz2.yy)>=0 && ccw(sz2.xx, sz1.yy, sz2.yy)<=0;
}
int main() {
int n;
cin>>n;
vector<pt> t(n);
for(int i=0;i<n;++i) cin>>t[i].xx>>t[i].yy;
//cerr<<diameter(t)<<"\n";
double L=0, R=diameter(t)/2;
for(int it=0;it<=64;++it) {
double mid=(L+R)/2;
//cerr<<L<<" "<<R<<"\n";
vector<pt> uj;
for(int i=0;i<n;++i) {
int a=(i-1+n)%n;
int b=(i+1)%n;
double alpha=angle(t[a], t[i], t[b]);
double x=mid/cos(alpha-PI/2);
pt v1={t[i].xx-t[a].xx, t[i].yy-t[a].yy};
pt v2={t[i].xx-t[b].xx, t[i].yy-t[b].yy};
v1=egyseg(v1);
v2=egyseg(v2);
uj.push_back({t[i].xx-x*(v1.xx+v2.xx), t[i].yy-x*(v1.yy+v2.yy)});
}
bool ok=true;
for(int i=0;i<n;++i) {
int a=(i+1)%n;
ok&=!intersect({t[i], uj[i]}, {t[a], uj[a]});
}
if(diameter(uj)>=2*mid && ok) {
L=mid;
}else {
R=mid;
}
}
cout<<fixed<<setprecision(3)<<L<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 3 |
Incorrect |
11 ms |
256 KB |
Output isn't correct |
| 4 |
Incorrect |
22 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
1489 ms |
632 KB |
Output isn't correct |
| 6 |
Execution timed out |
4099 ms |
1180 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4070 ms |
1352 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4086 ms |
1396 KB |
Time limit exceeded |
| 9 |
Execution timed out |
4002 ms |
2056 KB |
Time limit exceeded |
| 10 |
Execution timed out |
4019 ms |
1912 KB |
Time limit exceeded |
