POJ 3525 半平面交+二分

二分所能形成圆的最大距离，然后将每一条边都向内推进这个距离，最后所有边组合在一起判断时候存在内部点

 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 #include <cmath> using namespace std;
 #define N 105
 #define ll long long
 #define eps 1e-7 int dcmp(double x)
 {
     if(fabs(x)<eps) return ;
     else return x<?-:;
 } struct Point{
     double x,y;
     Point(double x= , double y=):x(x),y(y){}
 }p[N] , poly[N]; typedef Point Vector; struct Line{
     Point p;
     Vector v;
     double ang;
     Line(){}
     Line(Point p , Vector v):p(p),v(v){ang = atan2(v.y , v.x);}
     bool operator<(const Line &m) const{
         return dcmp(ang-m.ang)<;
     }
 }line[N]; Vector operator+(Vector a , Vector b){return Vector(a.x+b.x , a.y+b.y);}
 Vector operator-(Vector a , Vector b){return Vector(a.x-b.x , a.y-b.y);}
 Vector operator*(Vector a , double b){return Vector(a.x*b , a.y*b);}
 Vector operator/(Vector a , double b){return Vector(a.x/b , a.y/b);} double Cross(Vector a , Vector b){return a.x*b.y-a.y*b.x;}
 double Dot(Vector a , Vector b){return a.x*b.x+a.y*b.y;}
 double Len(Vector a){return sqrt(Dot(a,a));} bool OnLeft(Line L , Point P)
 {
     return dcmp(Cross(L.v , P-L.p))>;
 } Point GetIntersection(Line a , Line b)
 {
     Vector u = a.p-b.p;
     double t = Cross(b.v , u)/Cross(a.v , b.v);
     return a.p+a.v*t;
 } Vector Normal(Vector a)
 {
     double l = Len(a);
     return Vector(-a.y , a.x)/l;
 } int HalfplaneIntersection(Line *L , int n , Point *poly)
 {
     sort(L , L+n);
     int first , last;
     Point *p = new Point[n];
     Line *q = new Line[n];
     q[first=last=] = L[];
     for(int i= ; i<n ; i++){
         while(first<last && !OnLeft(L[i] , p[last-])) last--;
         while(first<last && !OnLeft(L[i] , p[first])) first++;
         q[++last] = L[i];
         if(fabs(Cross(q[last].v , q[last-].v))<eps){
             last--;
             if(OnLeft(q[last] , L[i].p)) q[last]=L[i];
         }
         if(first < last) p[last-] = GetIntersection(q[last-] , q[last]);
     }
     while(first<last && !OnLeft(q[first] , p[last-])) last--;
     if(last-first<=) return ;
     p[last] = GetIntersection(q[last] , q[first]);
     int m=;
     for(int i=first ; i<=last ; i++) poly[m++] = p[i];
     return m;
 } double calArea(Point *p , int n)
 {
     if(!n) return ;
     double ret = ;
     for(int i= ; i<n ; i++){
         ret += Cross(p[i-]-p[],p[i]-p[]);
     }
     return ret/;
 } double bin_search(Point *p , int n)
 {
     double l =  , r = 1e8 , m;
     Vector unit;
     while(r-l>=eps)
     {
         m = (l+r)/;
         for(int i= ; i<=n ; i++){
             unit = Normal(p[i]-p[i-]);
             line[i-] = Line(p[i-]+unit*m , p[i]-p[i-]);
         }
         if(HalfplaneIntersection(line , n , poly)) l=m;
         else r=m;
     }
     return l;
 } int main()
 {
    // freopen("in.txt" , "r" , stdin);
     int n ;
     while(scanf("%d" , &n) , n)
     {
         for(int i= ; i<n ; i++) scanf("%lf%lf" , &p[i].x , &p[i].y);
         p[n] = p[];
         printf("%.6f\n" , bin_search(p , n));
     }
 }