POJ3525 Most Distant Point from the Sea

题意

考虑二分答案(mid)，之后将所有向量向内缩(mid)距离，之后判断半平面是否存在即可。

code:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
const double eps=1e-8;
const double Pi=acos(-1.0);
const double inf=150000;
int T,n;
struct Point
{
    double x,y;
    Point(double _x=0,double _y=0){x=_x,y=_y;}
    inline double len(){return sqrt(x*x+y*y);}
    Point operator+(const Point a)const{return Point(x+a.x,y+a.y);}
    Point operator-(const Point a)const{return Point(x-a.x,y-a.y);}
    Point operator*(double k)const{return Point(x*k,y*k);}
    Point operator/(double k)const{return Point(x/k,y/k);}
    double operator*(const Point a)const{return x*a.y-y*a.x;}
    double operator&(const Point a)const{return x*a.x+y*a.y;}
}p[maxn];
inline int dcmp(double x)
{
    if(fabs(x)<=eps)return 0;
    return x<0?-1:1;
}
inline Point get(Point a,Point b){return b-a;}
inline Point turn(Point a,double theta){return Point(a.x*cos(theta)-a.y*sin(theta),a.x*sin(theta)+a.y*cos(theta));} 
struct Line
{
    Point p,v;double theta;
    Line(Point _p=Point(),Point _v=Point()){p=_p,v=_v;}
    bool operator<(const Line a)const
    {
        return (!dcmp(theta-a.theta))?(dcmp(get(p,v)*get(p,a.v))<0):(dcmp(theta-a.theta)<0);
    } 
}line[maxn],q[maxn];
inline Point getpoint(Line a,Line b)
{
    Point p1=a.p,p2=b.p,v1=a.v,v2=b.v;
    v1=get(p1,v1),v2=get(p2,v2);
    Point u=get(p1,p2);
    return p2+v2*(u*v1)/(v1*v2);
}
inline bool check(Line a,Line b,Line c)
{
    Point p=getpoint(a,b);
    return dcmp(get(c.p,c.v)*get(c.p,p))<0;
}
inline bool calc()
{
    for(int i=1;i<=n;i++)line[i].theta=atan2(line[i].v.y-line[i].p.y,line[i].v.x-line[i].p.x);
    sort(line+1,line+n+1);
    int cnt=0;line[0].theta=inf;
    for(int i=1;i<=n;i++)if(line[i].theta!=line[i-1].theta)line[++cnt]=line[i];
    int l,r;
    q[l=r=1]=line[1];q[++r]=line[2];
    for(int i=3;i<=cnt;i++)
    {
        while(l<r&&check(q[r-1],q[r],line[i]))r--;
        while(l<r&&check(q[l],q[l+1],line[i]))l++;
        q[++r]=line[i];
    }
    while(l<r&&check(q[r-1],q[r],q[l]))r--;
    while(l<r&&check(q[l],q[l+1],q[r]))l++;
    return r-l+1>=3;
}
inline void change(Line& a,double mid)
{
    Point dir=get(a.p,a.v)/get(a.p,a.v).len();
    dir=turn(dir,Pi/2.0);
    a.p=a.p+(dir*mid),a.v=a.v+(dir*mid);
}
inline bool check_ans(double mid)
{
    for(int i=1;i<=n;i++)line[i]=Line(p[i],p[i+1]);
    for(int i=1;i<=n;i++)change(line[i],mid);
    return calc();
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
        p[n+1]=p[1];
        double l=0,r=inf;
        while(dcmp(r-l)>0)
        {
            double mid=(l+r)*0.5;
            if(check_ans(mid))l=mid;
            else r=mid;
        }
        printf("%.6lf
",l);
    }
    return 0;
}