[BZOJ3707] 圈地

神题

题意

n个不共点的点,选至少3个点使围成多边形面积最小。

思路

显然选3个点。

写个 $ \Theta(n ^ 3) $ 没有希望。

考虑个 $ \Theta(n ^ 2) $ 的做法。

枚举每条线段,如果把一条线段旋转到y轴上,然后面积最小的情况是和y轴两边最近的点组成三角形方案的其中之一。

显然把线段按斜率排序,把点按(x,y)排序。

考虑一条新转移线段和前一条线段,显然两线段间无其他线段,只有现在的两个端点互换位置。

Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
const int N = 1010,M = (N * N) >> 1;const double eps = 1e-8,inf = 1e50;
inline double safediv(double a,double b){return fabs(b) <= eps ? inf : (a / b);}
struct point
{
double x,y;
inline point(double x = 0.0,double y = 0.0):x(x),y(y){}
inline friend bool operator < (const point &a,const point &b){return a.x == b.x ? a.y < b.y : a.x < b.x;}
}po[N];
struct segment
{
double k;int idx,idy;
inline segment(double k = 0.0,int idx = 0,int idy = 0):k(k),idx(idx),idy(idy){}
inline segment(point x,point y,int idx,int idy)
{
k = safediv(y.y - x.y,y.x - x.x);
this->idx = idx,this->idy = idy;
}
inline friend bool operator < (const segment &a,const segment &b){return a.k < b.k;}
}li[N * N / 2];
int n,m;int pos[N],id[N];
inline double cross(point a,point b,point c)
{
double x1 = b.x - a.x,y1 = b.y - a.y,x2 = c.x - a.x,y2 = c.y - a.y;
return fabs(x1 * y2 - x2 * y1);
}
double ans = 1e60;
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i) scanf("%lf%lf",&po[i].x,&po[i].y);
std::sort(po + 1,po + n + 1);
for(int i = 1;i <= n;++i) id[i] = pos[i] = i;
for(int i = 1;i <= n;++i) for(int j = 1;j < i;++j) li[++m] = segment(po[j],po[i],j,i);
std::sort(li + 1,li + m + 1);
for(int i = 1;i <= m;++i)
{
int a = li[i].idx,b = li[i].idy;
if(id[a] > id[b]) std::swap(id[a],id[b]);
if(id[a] > 1) ans = std::min(ans,cross(po[pos[id[a] - 1]],po[a],po[b]));
if(id[b] < n) ans = std::min(ans,cross(po[pos[id[b] + 1]],po[a],po[b]));
std::swap(id[a],id[b]);std::swap(pos[id[a]],pos[id[b]]);
}
printf("%.2lf\n",ans / 2);
return 0;
}