题解 BZOJ 3707 圈地 计算几何

题解:

简单的说就是给定平面上n个点,求这n个点组成三角形的最小面积。

如果分别枚举三个点的话是$O(n^3)$的,时间无法承受。

如果枚举了两个点a,b。设它们间的距离是L。如果以点a,b所在直线为y轴的话,与其他点所组成的三角形的面积$S=L*|x|/2$,x是其他点在这个坐标系中的横坐标。可以看出面积最小的就是离这个坐标系y轴最近的一个点。如果我们能够快速的得知最近的点的话,就可以将复杂度降低到$O(n^2)$。

把这些点两两之间求出一条直线,记录这条直线是哪两个点取到的,记录这条直线的斜率k。然后按照k排序,我们可以依次按照k递增连续变化的顺序处理这些直线。

首先将这些点按x坐标排序,相当于按x=0直线排序的情况,考虑由两个相邻的斜率k1变到k2时,这个序列的改变只有k1直线的两个点的顺序交换了下,其它点之间的顺序都没变。在枚举直线时,交换两点维护序列即可。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
//by zrt
//problem:
using namespace std;
typedef long long LL;
const int inf(0x3f3f3f3f);
const double eps(1e-9);
struct point{
int x,y;
friend bool operator < (point x,point y){
return x.x<y.x;
}
}p[1005];
struct line{
int x,y;double k;
friend bool operator < (line a,line b){
return a.k<b.k;
}
}l[500005];
int pos[1005],rank[1005];
int n,c;
double ans;
point operator -(point a,point b){
static point ret;
ret.x=a.x-b.x;
ret.y=a.y-b.y;
return ret;
}
double cross(point a,point b){
return a.x*1.0*b.y-b.x*1.0*a.y;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ans=1e200;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&p[i].x,&p[i].y);
}
sort(p+1,p+1+n);
for(int i=1;i<=n;i++) rank[i]=pos[i]=i;
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
l[++c].x=i;l[c].y=j;
l[c].k=(p[j].y-p[i].y)/(double)(p[j].x-p[i].x);
}
}
sort(l+1,l+c+1);
int a,b;
for(int i=1;i<=c;i++){
a=l[i].x;b=l[i].y;
if(pos[a]>pos[b]) swap(a,b);
if(pos[a]>1)ans=min(ans,fabs(cross(p[a]-p[b],p[rank[pos[a]-1]]-p[b])));
if(pos[b]<n)ans=min(ans,fabs(cross(p[a]-p[b],p[rank[pos[b]+1]]-p[b])));
swap(pos[a],pos[b]);
swap(rank[pos[a]],rank[pos[b]]);
}
printf("%.2f\n",ans/2.0);
return 0;
}
评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框