http://acmicpc-live-archive.uva.es/nuevoportal/先预处理所有凸包，然后dp。
1 #include<iostream>
2#include<cmath>
3#include<algorithm>
4#include<complex>
5#include<vector>
6#include<stdio.h>
7using namespace std;
8typedef complex<double> point;
9const int maxn = 530;
10const double eps = 1e-8;
11const double inf = 1e10;
12const double pi = acos( -1.0 );
13double dp[maxn];
14int c[10];
15  bool cmp( point p1, point p2 ) { return real(p1) < real(p2) || real(p1) == real(p2) && imag(p1) < imag(p2); }
16double operator^( point p1, point p2 ){ return imag( conj( p1 ) * p2 ); }
17int dblcmp( double x ){ return x < -eps ? -1 : x > eps ; }
18double minn( double x, double y ){ return x < y ? x : y; }
19void convex_hull( vector<point> &p, vector<point> &poly )
20{
21 int sz = 0, i, k;
22 poly.clear( );
23 sort( p.begin( ), p.end( ), cmp );
24 for( i = 0; i < p.size( ); ++i )
25  {
26 while( sz >= 2 && dblcmp( poly[sz-2] - p[i] ^ poly[sz-1] - p[i] ) <= 0 )
27 poly.pop_back( ), sz--;
28 poly.push_back( p[i] );
29 sz++;
30 }
31 k = sz;
32 for( i = p.size( ) - 2; i >= 0; i-- )
33 {
34 while( sz > k && dblcmp( poly[sz-2] - p[i] ^ poly[sz-1] - p[i] ) <= 0 )
35 poly.pop_back( ), sz--;
36 poly.push_back( p[i] );
37 sz++;
38 }
39 poly.pop_back( );
40 }
41
42int main( )
43{
44 double a[maxn], x, y;
45 int i, j, q, n, m, len, k = 1, sz;
46 vector<point> p, poly, poly1;
47 while( 1 )
48 {
49 p.clear( );
50 scanf("%d%d",&n,&m);
51 if( n == 0 && m == 0 )break;
52 for( i = 0; i < n; i++ )
53 {
54 scanf("%lf%lf",&x,&y);
55 p.push_back( point( x, y ) );
56 }
57 len = 1 << n;
58 for( i = 1; i < len; i++ )
59 {
60 poly.clear( );
61 poly1.clear( );
62 j = i; q = 0;
63 while( j )
64 {
65 if( j & 1 ) poly.push_back( p[q] );
66 q++;
67 j >>= 1;
68 }
69 convex_hull( poly, poly1 );
70 sz = poly1.size( );
71 for( a[i] = 2 * pi * m, j = 0; j < sz; j++ )
72 a[i] += abs( poly1[j] - poly1[(j+1)%sz] );
73 }
74 for( dp[0] = 0.0, i = 1; i < len; i++ )
75 dp[i] = inf;
76 for( i = 0; i < len; i++ )
77 for( j = 1; j < len; j++ )
78 if( ( j & i ) == 0 )
79 dp[i|j] = minn( dp[i] + a[j], dp[i|j] );
80 printf("Case %d: length = %.2lf\n",k++,dp[len-1]);
81 }
82 return 0;
83}
84
|