随笔-21  评论-10  文章-21  trackbacks-0
 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, -1sizeof(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 阅读(239) 评论(0)  编辑 收藏 引用 所属分类: geometry

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理