传送门
Problem
给出平面上的
n
n
n 个点，你需要从中选出不超过
k
k
k 个点，使得这些点构成的多边形面积最大。
数据范围：
0
<
n
≤
30
0 < n \leq 30
0<n≤30，
0
<
k
≤
30
0 < k \le 30
0<k≤30。
Solution
首先有两个比较显然的结论：
这
k
k
k 个点肯定是在凸包上选。在凸包上选
k
k
k 个点肯定比选
i
(
i
<
k
)
i(i<k)
i(i<k) 个点优。
因此，我们先做出凸包，然后在凸包上进行
d
p
dp
dp。
设
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k] 表示凸包上第
i
i
i 个点到第
j
j
j 个点中选
k
k
k 个的最大面积，那么有以下转移：
f
[
i
]
[
j
]
[
k
]
=
max
l
=
i
+
k
−
2
j
{
f
[
i
]
[
l
]
[
k
−
1
]
+
a
r
e
a
(
p
i
,
p
j
,
p
l
)
}
f[i][j][k]=\max_{l=i+k-2}^{j}\{f[i][l][k-1]+area(p_i,p_j,p_l)\}
f[i][j][k]=l=i+k−2maxj{f[i][l][k−1]+area(pi,pj,pl)}
其中
a
r
e
a
area
area 表示面积，
p
i
p_i
pi 表示
i
i
i 这个点。
发现在固定
i
i
i 时，第一维是固定的，可以优化掉（代码中没有去掉第一维）。
剩下的细节问题可以看代码。
Code
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 105
#define eps 1e-10
using namespace std
;
int n
,K
,top
;
int sgn(double x
) {return x
>eps
?1:(x
<-eps
?-1:0);}
struct point
{
double x
,y
;
point(double _x
=0,double _y
=0):x(_x
),y(_y
){}
friend point
operator+(const point
&a
,const point
&b
) {return point(a
.x
+b
.x
,a
.y
+b
.y
);}
friend point
operator-(const point
&a
,const point
&b
) {return point(a
.x
-b
.x
,a
.y
-b
.y
);}
friend double dot(const point
&a
,const point
&b
) {return a
.x
*b
.x
+a
.y
*b
.y
;}
friend double cross(const point
&a
,const point
&b
) {return a
.x
*b
.y
-a
.y
*b
.x
;}
}p
[N
],stk
[N
];
double f
[N
][N
][N
];
bool operator<(const point
&a
,const point
&b
){
double now
=cross(a
-p
[1],b
-p
[1]);
return sgn(now
)==0?a
.x
<b
.x
:sgn(now
)>0;
}
void Graham(){
int pos
=1;
for(int i
=2;i
<=n
;++i
)
if(p
[pos
].x
>p
[i
].x
||(p
[pos
].x
==p
[i
].x
&&p
[pos
].y
>p
[i
].y
))
pos
=i
;
swap(p
[pos
],p
[1]),sort(p
+2,p
+n
+1);
stk
[++top
]=p
[1],stk
[++top
]=p
[2];
for(int i
=3;i
<=n
;++i
){
while(top
>1&&sgn(cross(p
[i
]-stk
[top
-1],stk
[top
]-stk
[top
-1]))>=0) top
--;
stk
[++top
]=p
[i
];
}
stk
[top
+1]=stk
[1];
}
double area(point a
,point b
,point c
){
return fabs(cross(a
-b
,c
-b
))/2;
}
int main(){
int T
;
scanf("%d",&T
);
while(T
--){
scanf("%d%d",&n
,&K
);
for(int i
=1;i
<=n
;++i
)
scanf("%lf%lf",&p
[i
].x
,&p
[i
].y
);
top
=0,Graham();
if(top
<=2&&K
<=2) {puts("0.00");continue;}
double ans
=0;
if(top
<=K
){
for(int i
=1;i
<=top
;++i
)
ans
+=cross(stk
[i
],stk
[i
+1]);
printf("%lf\n",ans
/2);
continue;
}
for(int i
=1;i
<=n
;++i
){
memset(f
[i
],0,sizeof(f
[i
]));
point temp
=stk
[1];
for(int j
=1;j
<top
;++j
) stk
[j
]=stk
[j
+1];
stk
[top
]=temp
;
for(int j
=3;j
<=top
;++j
){
for(int k
=3;k
<=j
&&k
<=K
;++k
)
for(int l
=k
-1;l
<=j
;++l
)
f
[i
][j
][k
]=max(f
[i
][j
][k
],f
[i
][l
][k
-1]+area(stk
[1],stk
[l
],stk
[j
]));
ans
=max(ans
,f
[i
][j
][K
]);
}
}
printf("%.2lf\n",ans
);
}
return 0;
}
