http://acm.hdu.edu.cn/showproblem.php?pid=3372

太晚了，先贴代码。。。


  1#include<iostream>
  2#include<cmath>
  3#include<complex>
  4#include<algorithm>
  5#include<cstdio>
  6#include<cstring>
  7#include<cstdlib>
  8#include<cassert>
  9#define MAXN 20
 10using namespace std;
 11typedef complex<double> point;
 12const double eps = 1e-8;
 13const double pi = acos( -1.0 );
 14
 15double operator^( point p1, point p2 ){ return imag( conj( p1 ) * p2 ); }
 16int dblcmp( double x ){ return ( x < -eps ? -1 : x > eps ); }
 17bool com( point p1, point p2 )
 18{
 19    return dblcmp( p1.real( ) - p2.real( ) ) < 0 ||
 20        dblcmp( p1.real( ) - p2.real( ) ) == 0 && dblcmp( p1.imag( ) - p2.imag( ) ) < 0;
 21}
 22point p[MAXN],np[MAXN],out[MAXN];
 23int N,Ns;
 24int num1[MAXN],num2[MAXN];//记录哪几个点被使用了
 25
 26int compute( int n, int q )
 27{
 28    int j,i=0,k=0;
 29    for( j=0; j<n; j++ )
 30    {
 31        if( q & 1 ) num1[i++] = j;
 32        else num2[k++] = j; 
 33        q >>= 1;
 34    }
 35    return i;   //返回选出来圆的个数
 36}
 37//求凸包
 38void convex_hull( int n )
 39{
 40    int i,k;
 41    if( n<=2 )
 42    {
 43        for( i=0; i<n; i++ )
 44            np[i] = p[i];
 45        Ns = n;
 46        return ;
 47    }
 48    sort( p, p+n, com );
 49    Ns = 0;
 50    for( i=0; i<n; i++ )
 51    {
 52        while( Ns >= 2 && dblcmp( np[Ns-1] - np[Ns-2] ^ p[i] - np[Ns-1] ) <= 0 )
 53            Ns--;             //只有极点，改为<则包括所有共线点
 54        np[Ns++] = p[i];
 55    }
 56    k = Ns;
 57    for( i = n-2; i >= 0; i-- )
 58    {
 59        while( Ns > k && dblcmp( np[Ns-1] - np[Ns-2] ^ p[i] - np[Ns-2] ) <= 0 )
 60            Ns--;
 61        np[Ns++] = p[i];
 62    }
 63    Ns--;
 64}
 65
 66//点到线段距离   p到线段l1l2距离
 67double disptoseg( point p0, point l1, point l2 )
 68{
 69    point t = p0;
 70    t.real( l1.imag( ) - l2.imag( ) );
 71    t.imag( l2.real( ) - l1.real( ) );
 72    if( dblcmp( ( l1 - p0 ^ t - p0 ) * ( l2 - p0 ^ t - p0 ) ) > 0 )
 73        return abs( p0 - l1 ) < abs( p0 - l2 ) ? abs( p0 - l1 ) : abs( p0 - l2 ); 
 74    return fabs( p0 - l1 ^ p0 - l2 ) / abs( l1 - l2 );
 75}
 76
 77bool point_in_polygon( const point &p0, const double &area2 )
 78{
 79    int i;
 80    double area1 = 0.0;
 81    if( Ns == 2 )
 82        return dblcmp( real( conj( np[0] - p0 ) * ( p0 - np[1] ) ) ) >= 0 ;
 83    for( i = 0; i < Ns; i++ )
 84    {
 85        area1 += fabs( np[i] - p0 ^ np[i+1] - p0 );
 86    }
 87    if( area1 - fabs( area2 ) > eps ) return false;
 88    return true;
 89}
 90
 91bool touch( int n, const double &d )
 92{
 93    int i,j;
 94    double len;
 95    for( i = 0; i < n; i++ )
 96    {
 97        for( j = 0; j < Ns; j++ )
 98        {
 99            len = disptoseg( out[i], np[j], np[j+1] );
100            if( len - d < eps )return true;
101        }
102    }
103    return false;
104}
105
106int main( )
107{ 
108    point pp[MAXN];
109    double d,r,L,carea,maxarea,area,len,x,y,C;
110    int i,j,max,n,t,k,q;
111    //freopen("1.in","r",stdin);
112    //freopen("out.txt","w",stdout);
113    scanf("%d",&t);
114    while( t-- )
115    {
116        scanf("%d%lf%lf",&n,&d,&L);
117        for( i=0; i<n; i++ )
118        {
119            scanf("%lf%lf",&x,&y);
120            pp[i].real( x );
121            pp[i].imag( y );
122            p[i] = pp[i];
123        }
124        r = d / 2.0;
125        C = pi * d;
126        carea = pi * r * r ;
127
128        convex_hull( n );
129        len = 0.0;
130        np[Ns] = np[0];
131        for( j = 0; j < Ns; j++ )
132            len += abs( np[j] - np[j+1] );
133
134        if( L - ( len + C ) > -eps )
135        {
136            area = 0.0; 
137            for( j = 0; j < Ns; j++ )
138                area += np[j] ^ np[j+1];
139            area = fabs( area ) / 2.0 + len * r - ( n - 1 ) * carea;
140            if( area > 0 ) maxarea = area;
141        }
142        else 
143        {
144            max = ( 1 << n );
145            maxarea = 0.0;
146            for( i = max-1; i > 0; i-- )
147            {
148                k = compute( n, i );
149                q = n - k;
150                for( j = 0; j < k; j++ )
151                    p[j] = pp[ num1[j] ];
152
153                for( j = 0; j < q; j++ )  //外部的点
154                    out[j] = pp[ num2[j] ];
155
156                convex_hull( k );
157                len = 0.0;
158                np[Ns] = np[0];
159                for( j = 0; j < Ns; j++ )
160                    len += abs( np[j] - np[j+1] );
161                if( L - ( len + C ) > -eps )
162                {
163                    area = 0.0; 
164                    for( j = 0; j < Ns; j++ )
165                        area += np[j] ^ np[j+1];
166
167                    k = 0;
168                    for( j = 0; j < n; j++ )
169                        if( point_in_polygon( pp[j], area ) )
170                            k++;
171
172                    area = fabs( area ) / 2.0 + len * r - ( k - 1 ) * carea;
173                    if( area > maxarea && !touch( q, d ) ) maxarea = area;
174                }
175            }
176        }
177        printf("%.3lf\n",maxarea);
178    }
179    return 0;
180}