【poj1259】计几模板 最大空凸包

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 const int N= 109;
 8 struct Point{
 9     int x,y;
10     int operator ^ (const Point& b)const{
11         return x*b.y - b.x*y;
12     }
13     int cross (const Point& p1,const Point& p2)const{
14         return (p1.x - x) * (p2.y - y) - (p2.x - x) * (p1.y - y);
15     }
16     int len()const{return x*x + y*y;}
17     //极角排序，注意极角同时比len不要只比x坐标
18     bool operator < (const Point& b)const{
19         if( ((*this) ^ b) != 0 ) return ((*this) ^ b) > 0;
20         return len() < b.len();
21     }
22     Point operator - (const Point& b)const{
23         return (Point){x-b.x,y-b.y};
24     }
25 }p[N],a[N];
26 int dp[N][N];
27 int solve(Point p[],int m){
28     memset(dp,0,sizeof(dp));
29     int res = 0;
30     for(int i = 2;i <= m;++i){
31         int now = i-1;
32         //不能共线
33         while(now >= 1 && (p[i] ^ p[now]) == 0 ) --now;
34         //标记与下一个点是否共线
35         bool fg = 0;
36         if(now == i-1) fg = 1;
37         while(now  >= 1){
38             int S = (p[now] ^ p[i] );
39             int k = now - 1;
40             //维护凸性
41             while( k >= 1 && ( p[i].cross(p[now],p[k]) ) >  0) --k;
42             //这个dp[now][k]是更新过的 now第一边，第二边<=k
43             if(k>=1) S += dp[now][k];
44             res = max(res,S);
45             //这个dp[i][now] 为第一边为i，第二边为now
46             if(fg) dp[i][now] = S;
47             now = k;
48         }
49         //第一边为i，第二边<=j
50         for(int j = 1;j<i;++j) dp[i][j] = max(dp[i][j],dp[i][j-1]);
51     }
52     return res;
53 }
54 int main(){
55     int T; scanf("%d",&T);
56     while(T--){
57         int n;
58         scanf("%d",&n);
59         for(int i = 1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
60         int ans = 0;
61         for(int i = 1;i<=n;++i){
62             int cnt = 0;
63             //枚举凸包的左下角
64             for(int j = 1;j<=n;++j){
65                 if(a[j].y > a[i].y || (a[j].y == a[i].y && a[j].x >= a[i].x) ) p[++cnt] = a[j] - a[i];
66             }
67             sort(p+1,p+1+cnt);
68             ans = max(ans,solve(p,cnt));
69         }
70         printf("%.1f\n",ans/2.0);
71     }
72     return 0;
73 }