POJ 3525 半平面交

题意：

求多边形的最大内接圆。

题解：

二分答案，将所有边向内部逼近，当面积为恰好0时即为最大半径

终于写a了一会。。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

#define N 222
#define PI 3.14159265358979
#define INF 1e9
#define EPS 1e-7

using namespace std;

struct PO 
{
    double x,y;
}p[N],s[N],tp[N],f[N];

struct LI
{
    PO a,b;
}li[N],sl[N];

int n;

inline void prt(PO &a)
{
    printf("%lf    %lf\n",a.x,a.y);
}

inline void read()
{
    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    p[1+n]=p[1];
}

inline int dc(double x)
{
    if(x>EPS) return 1;
    else if(x<-EPS) return -1;
    return 0;
}

inline PO operator -(PO a,PO b)
{
    PO c;
    c.x=a.x-b.x; c.y=a.y-b.y;
    return c;
}

inline PO rotate(PO a,double sss,double ccc)
{
    PO ans;
    ans.x=ccc*a.x-sss*a.y;
    ans.y=sss*a.x+ccc*a.y;
    return ans;
}

inline double getlen(PO &a)
{
    return sqrt(a.x*a.x+a.y*a.y);
}

inline PO getf(PO &a,PO &b)//得到ab左旋90度后的单位向量 
{
    PO ans;
    ans=b-a;
    ans=rotate(ans,sin(0.5*PI),cos(0.5*PI));
    double k=getlen(ans);
    ans.x/=k; ans.y/=k;
    return ans;
}

inline void prep()
{
    for(int i=1;i<=n;i++)
    {
        f[i]=getf(p[i],p[i+1]);
        li[i].a=p[i]; li[i].b=p[i+1];
    }
}

inline void move(double k)
{
    for(int i=1;i<=n;i++)
    {
        sl[i].a.x=li[i].a.x+k*f[i].x;
        sl[i].a.y=li[i].a.y+k*f[i].y;
        sl[i].b.x=li[i].b.x+k*f[i].x;
        sl[i].b.y=li[i].b.y+k*f[i].y;
    }
}

inline double cross(PO &a,PO &b,PO &c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

inline PO getpoint(PO &a,PO &b,PO &c,PO &d)//直线交点 
{
    PO ans,tp=b-a;
    double k1=cross(a,d,c);
    double k2=cross(b,c,d);
    ans.x=a.x+tp.x*k1/(k1+k2);
    ans.y=a.y+tp.y*k1/(k1+k2);
    return ans;
}

inline int getcut()
{
    tp[1].x=tp[5].x=-INF; tp[1].y=tp[5].y=-INF;
    tp[2].x=INF,tp[2].y=-INF;
    tp[3].x=INF,tp[3].y=INF;
    tp[4].x=-INF,tp[4].y=INF;
    int cp=4,tc;
    for(int i=1;i<=n;i++)
    {
        tc=0;
        for(int j=1;j<=cp;j++)
        {
            if(dc(cross(sl[i].a,sl[i].b,tp[j]))>=0) s[++tc]=tp[j];
            if(dc(cross(sl[i].a,sl[i].b,tp[j])*cross(sl[i].a,sl[i].b,tp[j+1]))<0)
                s[++tc]=getpoint(sl[i].a,sl[i].b,tp[j],tp[j+1]);
        }
        s[tc+1]=s[1];
        for(int j=1;j<=tc+1;j++) tp[j]=s[j];
        cp=tc;
    }
    return cp;
}

inline void go()
{
    prep();
    double l=0.0,r=10000000.0,mid,ans;
    int cs=100;
    while(cs--)
    {
        mid=(l+r)*0.5;
        move(mid);
        if(getcut()) l=mid,ans=mid;
        else r=mid;
    }
    printf("%.6lf\n",ans);
}

int main()
{
    while(scanf("%d",&n),n) read(),go();
    return 0;
}