Top

最大空凸包


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

/*
给你一堆点,求一个最大面积的空凸包,里面没有点.
*/

#include<bits/stdc++.h>
#define N 55
using namespace std;
struct rec
{
double x,y;
};
rec operator -(rec a,rec b)
{
rec c;
c.x=a.x-b.x;
c.y=a.y-b.y;
return c;
}
double sqr(double a)
{
return a*a;
}
int sign(double a)
{
if (fabs(a) <= 1e-6) return 0;
return a<0?-1 :1;
}
bool operator <(rec a,rec b)
{
return sign(b.y-a.y)>0 || sign(b.y-a.y)==0 && sign(b.x-a.x)>0;
}
double max(double a,double b)
{
return a>b ?a:b;
}
double length(rec a)
{
return sqrt(sqr(a.x)+sqr(a.y));
}
double cross(rec a,rec b)
{
return a.x*b.y-a.y*b.x;
}
rec dot[N],lis[N];
double opt[N][N];
int seq[N],n,len;
double ans;
bool Compare(rec a,rec b)
{
int temp=sign(cross(a,b));
if (temp!=0) return temp>0;
temp=sign(length(b)-length(a));
return temp>0;
}
void solve(int vv)
{
int t,i,j,_len;
for (i=len=0;i<n;i++)
if (dot[vv]<dot[i]) lis[len++]=dot[i]-dot[vv];
for (int i=0;i<len;i++)
for (int j=0;j<len;j++)
opt[i][j]=0;
sort(lis,lis+len,Compare);
double v;
for (t=1;t<len;t++)
{
_len=0;
for (i=t-1;i>=0 && sign(cross(lis[t],lis[i])) ==0 ;i--);
while (i>=0)
{
v=cross(lis[i],lis[t])/2;
seq[_len++]=i;
for (j=i-1; j>=0 && sign(cross(lis[i]-lis[t], lis[j]-lis[t])) >0 ;j--);
if (j>=0) v+=opt[i][j];
ans=max(ans,v);
opt[t][i]=v;
i=j;
}
for (i = _len-2;i>=0;i--)
opt[t][seq[i]]=max(opt[t][seq[i]],opt[t][seq[i+1]]);
}
}
int T;
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=0;i<n;i++) scanf("%lf%lf",&dot[i].x,&dot[i].y);
ans=0;
for (int i=0;i<n;i++) solve(i);
printf("%.1lf\n",ans);
}
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址