1 /*
2 23:15 - 0:22
3 12:10 - 12:46
4 22:00 - 0:00
5 總共3:30小時
6 1 由于點集是圍繞原點逆時針排好序，直接可以graham
7 2 dp[i][j][k]表示用i根皮筋去綁以i開始的連續j個點的最小面積，狀態清晰
8 3 代碼中能做優化是很強大的能力
9 */
10
11 #include<iostream>
12 #include<cstring>
13 #include<cstdio>
14 #include<algorithm>
15 #include<cmath>
16 using namespace std;
17
18 const int maxn = 150;
19
20 struct Point{
21 int x, y;
22 bool operator<(const Point &a)const
23 {
24 return atan2(y + 0.0, x + 0.0) < atan2(a.y + 0.0 , a.x + 0.0);
25 }
26 }p[maxn];
27 int B, N, area;
28 Point zero;
29 int dp[55][maxn][maxn];
30
31 int det(Point a, Point b, Point c){
32 return (a.x - c.x)*(b.y - c.y) - (a.y - c.y)*(b.x - c.x);
33 }
34
35 int calc(int from, int to){
36 int cnt = 0, area = 0;
37 Point stack[maxn];
38 for(int i = from; i < to; i++){
39 while(cnt >= 2 && det(p[i % N], stack[cnt-1], stack[cnt-2]) > 0)cnt--;
40 stack[cnt++] = p[i % N];
41 }
42 for(int i = 0; i < cnt-1; i++)
43 area += det(stack[i], stack[i+1], zero);
44 return area;
45 }
46
47 void solve(){
48 area = -1;
49 memset(dp, -1, sizeof(dp));
50 for(int i = 0; i < N; i++)
51 for(int j = 2; j <= N; j++){
52 if(det(p[i], p[(i+j-1)%N], zero) < 0)break;
53 dp[1][i][j] = calc(i, i + j);
54 //cout<<i<<" "<<j<<" "<<dp[1][i][j]<<endl;
55 }
56 for(int k = 2; k <= B; k++){
57 for(int i = 0; i < N; i++)
58 for(int j = 2*k; j <= N; j++)
59 {
60 for(int q = 2; q <= j - 2*(k-1); q++)
61 {
62 if(dp[k-1][(i+q)%N][j - q]==-1)continue;
63 if(dp[1][i][q]==-1)continue;
64 int t = dp[1][i][q] + dp[k-1][(i+q)%N][j - q];
65 if(t < dp[k][i][j] || dp[k][i][j]==-1)dp[k][i][j] = t;
66 }
67 }
68 }
69 for(int i = 0; i < N; i++)
70 if( dp[B][i][N]!=-1 && (dp[B][i][N] < area || area==-1) )
71 area = dp[B][i][N];
72 }
73
74 int main(){
75 zero.x = zero.y = 0;
76 while(scanf("%d %d",&B, &N) &&(B + N)){
77 int x0, y0;
78 scanf("%d %d",&x0, &y0);
79 for(int i = 0; i < N-1; i++){
80 scanf("%d %d",&p[i].x, &p[i].y);
81 p[i].x -= x0;
82 p[i].y -= y0;
83 }
84 sort(p, p + (--N) );
85 solve();
86 printf("%.2lf\n",area * 0.5);
87 }
88 }
89
posted on 2009-10-27 00:09
wangzhihao 閱讀(247)
評論(0) 編輯 收藏 引用 所屬分類:
geometry