首页 > 代码库 > BZOJ 3707: 圈地 计算几何
BZOJ 3707: 圈地 计算几何
Description
2维平面上有n个木桩，黄学长有一次圈地的机会并得到圈到的土地，为了体现他的高风亮节，他要使他圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形，多边形的顶点就是一个木桩，圈得的土地就是这个多边形内部的土地。（因为黄学长非常的神，所以他允许圈出的第n点共线，那样面积算0）
Input
第一行一个整数n，表示木桩个数。
接下来n行，每行2个整数表示一个木桩的坐标，坐标两两不同。
题解：
简单的说就是给定平面上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直线的两个点的顺序交换了下，其它点之间的顺序都没变。在枚举直线时，交换两点维护序列即可。
代码：
#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;}
BZOJ 3707: 圈地 计算几何
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。