http://acm.pku.edu.cn/JudgeOnline/problem?id=3525
半平面交

#include<iostream>
#include<deque>
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstdio>
#include<vector>
using namespace std;

const double PI = acos( -1.0 );
const double inf = 10000.0;
const double eps = 1e-8;
typedef complex<double> point;

double operator^( point a, point b ){ return imag( conj(a) * b ); }
int dblcmp( double x ){ return ( x < -eps )? -1 : x>eps ; }

struct line
{
    point a, b;
    double angle;
    line( ){ }
    line( point u, point v ):a( u ),b( v ){ angle = arg( b - a ); }
    bool operator<( const line &l ) const 
    {
        return dblcmp( angle-l.angle )<0 ||
            dblcmp( angle-l.angle )==0 && dblcmp( b-a^l.b-a )<0;
    }
};
deque<point> P;
deque<int> E;
vector<line> cut;
vector<point> pp;

point rotation( point p1, point p2, double r ) // 逆时针旋转90度,长度变为r
{
    point p;
    double t = r / abs( p2 - p1 );
    p.real( ( imag(p1) - imag(p2) ) * t );
    p.imag( ( real(p2) - real(p1) ) * t );
    return p;
}
bool onLeft( point p, line l ){    return ( l.b-l.a^p-l.a) >= 0; }//要有等号
point operator*( line l1, line l2 )
{
    double t = l1.a - l2.a^ l1.b - l2.a;
    double s = l1.b - l2.b^ l1.a - l2.b;
    return l2.a + ( l2.b - l2.a ) * t / ( t + s );
}
void MyUnique( )
{
    vector<line> tem;
    tem.push_back( cut[0] );
    for( int i = 1; i < cut.size( ); i++ )
    {
        if( dblcmp( tem.back( ).angle - cut[i].angle ) != 0 )
            tem.push_back( cut[i] );
    }
    cut = tem;
}
bool solve( )
{
    sort( cut.begin( ), cut.end( ) );
    MyUnique( );
    point last;
    bool ok = false; 
    for( int i = 0; i < cut.size( ); i++ )
    {
        int step = dblcmp( cut[i].angle - cut[0].angle -  PI );
        if( ok && onLeft( last, cut[i] ) )continue;
        while( !P.empty( ) && !onLeft( P.back( ), cut[i] ) ) P.pop_back( ), E.pop_back( );
        if( step >= 0 )
        {
            while( !P.empty( ) && !onLeft( P.front( ), cut[i]) ) P.pop_front( ), E.pop_front( );
            if( P.empty( ) )return false;
        }
        if( !E.empty( ) )P.push_back( cut[ E.back( ) ] * cut[i] );
        E.push_back( i );
        if( step > 0 )ok = true, last = cut[ E.front( ) ] * cut[ E.back( ) ];
    }
    P.push_back( last );
    return true;
}

int main( int argc, char *argv[] )
{
    int i,n,t,sz;
    double x,y,low,high,mid;
    point p;
    while( scanf("%d", &n) && n )
    {
        cut.clear( );
        P.clear( );
        E.clear( );
        pp.clear( ); 
        for( i = 0; i < n; i++ )
        {
            scanf("%lf %lf", &x, &y );
            pp.push_back( point( x, y ) );
            //cut.push_back( line( point( x1,y1 ), point( x2, y2 ) ) );
        }
        low=0.0, high = inf;
        while( dblcmp( low-high ) < 0 )
        {
            mid = ( low + high ) / 2.0;
            cut.clear( );
            P.clear( );
            E.clear( );
            sz=pp.size( );
            p = rotation( pp[sz-1], pp[0], mid );
            cut.push_back( line( pp[sz-1]+p, pp[0]+p ) );
            for( i=0; i<sz-1; i++ )
            {
                p = rotation( pp[i], pp[i+1], mid );
                cut.push_back( line( pp[i]+p, pp[i+1]+p ) );
            }
            if( solve( ) )
                low = mid;
            else high = mid;
        }
        printf("%lf\n",mid);
    }
    return 0;
}