#include <bits/stdc++.h>
using namespace std;
struct Point
{
long double x, y;
};
struct Line
{
Point p1, p2;
long double angle;
Line() {}
Line(Point a, Point b) : p1(a), p2(b)
{
angle=atan2l(b.y-a.y, b.x-a.x);
}
};
long double cross(Point a, Point b, Point c)
{
return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
Point intersect(Line l1, Line l2)
{
long double a1=l1.p2.y-l1.p1.y;
long double b1=l1.p1.x-l1.p2.x;
long double c1=-(a1*l1.p1.x+b1*l1.p1.y);
long double a2=l2.p2.y-l2.p1.y;
long double b2=l2.p1.x-l2.p2.x;
long double c2=-(a2*l2.p1.x+b2*l2.p1.y);
long double det=a1*b2-a2*b1;
return {(b1*c2-b2*c1)/det,(a2*c1-a1*c2)/det};
}
bool outside(Line l, Point p)
{
return cross(l.p1, l.p2, p)<-1e-10;
}
vector<Point> half_planes(vector<Line>& lines)
{
int n=lines.size();
if(n==0)
{
return {};
}
int start=0;
for(int i=1; i<n; i++)
{
if(lines[i].angle<lines[start].angle)
{
start=i;
}
}
vector<Line> sorted;
for(int i=0; i<n; i++)
{
sorted.push_back(lines[(start+i)%n]);
}
vector<Line> unique_lines;
for(int i=0; i<n; i++)
{
if(!unique_lines.empty() && fabsl(sorted[i].angle-unique_lines.back().angle)<1e-13)
{
if(outside(unique_lines.back(), sorted[i].p1))
{
unique_lines.back()=sorted[i];
}
continue;
}
unique_lines.push_back(sorted[i]);
}
deque<Line> dq;
for(int i=0; i<(int)unique_lines.size(); i++)
{
while(dq.size()>1 && outside(unique_lines[i], intersect(dq[dq.size()-1], dq[dq.size()-2])))
{
dq.pop_back();
}
while(dq.size()>1 && outside(unique_lines[i], intersect(dq[0], dq[1])))
{
dq.pop_front();
}
dq.push_back(unique_lines[i]);
}
while(dq.size()>2 && outside(dq[0], intersect(dq[dq.size()-1], dq[dq.size()-2])))
{
dq.pop_back();
}
while(dq.size()>2 && outside(dq[dq.size()-1], intersect(dq[0], dq[1])))
{
dq.pop_front();
}
if(dq.size()<3)
{
return {};
}
vector<Point> res;
for(int i=0; i<(int)dq.size(); i++)
{
res.push_back(intersect(dq[i], dq[(i+1)%dq.size()]));
}
return res;
}
long double dist(Point a, Point b)
{
return(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long double diameter(const vector<Point>& poly)
{
int n=poly.size();
if(n<2)
{
return 0;
}
if(n==2)
{
return sqrtl(dist(poly[0], poly[1]));
}
long double d=0;
int k=1;
for(int i=0; i<n; i++)
{
while(fabsl(cross(poly[i], poly[(i+1)%n], poly[(k+1)%n]))>fabsl(cross(poly[i], poly[(i+1)%n], poly[k])))
{
k=(k+1)%n;
}
d=max(d, sqrtl(dist(poly[i], poly[k])));
d=max(d, sqrtl(dist(poly[(i+1)%n], poly[k])));
}
return d;
}
bool fit(long double R, int N, const vector<Point>& pts)
{
vector<Line> shifted;
for(int i=0; i<N; i++)
{
Point p1=pts[i];
Point p2=pts[(i+1)%N];
long double dx=p2.x-p1.x, dy=p2.y-p1.y;
long double len=sqrtl(dx*dx+dy*dy);
if(len<1e-10)
{
continue;
}
long double nx=-dy/len, ny=dx/len;
shifted.push_back(Line({p1.x+R*nx, p1.y+R*ny}, {p2.x+R*nx, p2.y+R*ny}));
}
vector<Point> inner=half_planes(shifted);
return diameter(inner)>=2.0*R;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin>>N;
vector<Point> pts(N);
for(int i=0; i<N; i++)
{
cin>>pts[i].x>>pts[i].y;
}
long double low=0;
long double high=2e7;
for(int iter=0; iter<80; iter++)
{
long double mid=(low+high)/2.0;
if(fit(mid, N, pts))
{
low=mid;
}
else
{
high=mid;
}
}
cout<<fixed<<setprecision(3)<<(double)low<<endl;
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
