【POJ 3525】Most Distant Point from the Sea(直线平移、半平面交)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define dd double
#define eps 1e-5
#define N 505
using namespace std;
int n;
struct Point{
    dd x,y;
}p[N],tp[N],q[N];
dd osXoe(const Point &po,const Point &ps,const Point &pe){
    return (ps.x-po.y)*(pe.y-po.y)-(pe.x-po.x)*(ps.y-po.y);
}
void eq(const Point &p1,const Point &p2,dd &a,dd &b,dd &c){
    a=p2.y-p1.y;
    b=p1.x-p2.x;
    c=p2.x*p1.y-p1.x*p2.y;
}
Point cross(Point p1,Point p2,dd a,dd b,dd c){
    dd u=fabs(a*p1.x+b*p1.y+c);
    dd v=fabs(a*p2.x+b*p2.y+c);
    Point t;
    t.x=(p1.x*v+p2.x*u)/(u+v);
    t.y=(p1.y*v+p2.y*u)/(u+v);
    return t;
}
int Cut(dd a,dd b,dd c,int cnt){
    int tmp=0;
    for (int i=1;i<=cnt;i++){
        if(a*p[i].x+b*p[i].y+c>-eps)tp[++tmp]=p[i];
        else{
            if(a*p[i-1].x+b*p[i-1].y+c>eps)
                tp[++tmp]=cross(p[i-1],p[i],a,b,c);
            if(a*p[i+1].x+b*p[i+1].y+c>eps)
            tp[++tmp]=cross(p[i],p[i+1],a,b,c);
        }
    }
    for (int i=1;i<=tmp;i++)p[i]=tp[i];
    p[0]=p[tmp];p[tmp+1]=p[1];
    return tmp;
}
int solve(dd r){
    q[0]=q[n];q[n+1]=q[1];
    for (int i=0;i<=n+1;i++) p[i]=q[i];
    int cnt=n;
    for (int i=1;i<=n;i++){
        dd a,b,c;
        Point p1,p2,p3;
        p1.y=q[i+1].x-q[i].x;p1.x=q[i].y-q[i+1].y;
        dd k=r/sqrt(p1.x*p1.x+p1.y*p1.y);
        p1.x=k*p1.x;p1.y=k*p1.y;
//p1是垂直q[i+1]->q[i]指向右手边的长度为r的向量。如果是q[i]->q[i+1]则求指向左手边的。
        p2.x=p1.x+q[i].x;p2.y=p1.y+q[i].y;
        p3.x=p1.x+q[i+1].x;p3.y=p1.y+q[i+1].y;
        eq(p3,p2,a,b,c);//过p3->p2的直线方程ax+by+c=0
        cnt=Cut(a,b,c,cnt);//求半平面交剩下的点
    }
    return cnt;
}
int main(){
    while(cin>>n,n){
        for (int i=1;i<=n;i++)
            scanf("%lf%lf",&q[i].x,&q[i].y);
        dd l=0,r=1<<30,m;
        while(fabs(r-l)>eps){
            m=(l+r)/2.0;
            if(solve(m))l=m;
            else r=m;
        }
        printf("%.6f\n",m);
    }
}