2017ACM/ICPC亞洲區沈陽站 C Hdu-6219 Empty Convex Polygons 計算幾何最大空凸包

題面

題意:給你一堆點,求一個最大面積的空凸包,里面沒有點.

題解:紅書板子,照抄完事,因為題目給的都是整點,所以最后答案一定是.5或者.0結尾,不用對答案多做處理

? ?

 1 #include<bits/stdc++.h>
 2 #define N 55
 3 using namespace std;
 4 struct rec
 5 {
 6     double x,y;
 7 };
 8 rec operator -(rec a,rec b)
 9 {
10     rec c;
11     c.x=a.x-b.x;
12     c.y=a.y-b.y;
13     return c;
14 }
15 double sqr(double a)
16 {
17     return a*a;
18 }
19 int sign(double a)
20 {
21     if (fabs(a) <= 1e-6) return 0;
22     return a<0?-1 :1;
23 }
24 bool operator <(rec a,rec b)
25 {
26      return sign(b.y-a.y)>0 || sign(b.y-a.y)==0 && sign(b.x-a.x)>0;
27 }
28 double max(double a,double b)
29 {
30     return a>b ?a:b;
31 }
32 double length(rec a)
33 {
34     return sqrt(sqr(a.x)+sqr(a.y));
35 }
36 double cross(rec a,rec b)
37 {
38     return a.x*b.y-a.y*b.x;
39 }
40 rec dot[N],lis[N];
41 double opt[N][N];
42 int seq[N],n,len;
43 double ans;
44 bool Compare(rec a,rec b)
45 {
46     int temp=sign(cross(a,b));
47     if (temp!=0) return temp>0;
48     temp=sign(length(b)-length(a));
49     return temp>0;
50 }
51 void solve(int vv)
52 {
53     int t,i,j,_len;
54     for (i=len=0;i<n;i++)
55         if (dot[vv]<dot[i]) lis[len++]=dot[i]-dot[vv];
56     for (int i=0;i<len;i++)
57         for (int j=0;j<len;j++)
58             opt[i][j]=0;
59     sort(lis,lis+len,Compare);
60     double v;
61     for (t=1;t<len;t++)
62     {
63         _len=0;
64         for (i=t-1;i>=0 && sign(cross(lis[t],lis[i])) ==0   ;i--);
65         while (i>=0)
66         {
67             v=cross(lis[i],lis[t])/2;
68             seq[_len++]=i;
69             for (j=i-1; j>=0 && sign(cross(lis[i]-lis[t], lis[j]-lis[t])) >0 ;j--);
70             if (j>=0) v+=opt[i][j];
71             ans=max(ans,v);
72             opt[t][i]=v;
73             i=j;
74         }
75         for (i = _len-2;i>=0;i--)
76             opt[t][seq[i]]=max(opt[t][seq[i]],opt[t][seq[i+1]]);
77     }
78 }
79 int T;
80 int main()
81 {
82     scanf("%d",&T);
83     while (T--)
84     {
85         scanf("%d",&n);
86         for (int i=0;i<n;i++) scanf("%lf%lf",&dot[i].x,&dot[i].y);
87         ans=0;
88         for (int i=0;i<n;i++) solve(i);
89         printf("%.1lf\n",ans);
90     }
91     return 0;
92 }

轉載于:https://www.cnblogs.com/qywhy/p/9741184.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/450539.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/450539.shtml
英文地址，請注明出處：http://en.pswp.cn/news/450539.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！