首页 > 代码库 > [BZOJ]1069: [SCOI2007]最大土地面积
[BZOJ]1069: [SCOI2007]最大土地面积
题目大意:给出二维平面上n个点,求最大的由这些点组成的四边形面积。(n<=2000)
思路:求出凸包后旋转卡壳枚举对踵点对作为四边形的对角线,枚举或二分另外两个点,复杂度O(n^2)或O(nlogn)。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define MN 2000 #define eps 1e-7 struct P{double x,y;}p[MN+5]; P operator-(P a,P b){return (P){a.x-b.x,a.y-b.y};} double operator*(P a,P b){return a.x*b.y-a.y*b.x;} double area(P a,P b,P c){return fabs((b-a)*(c-a));} int dcmp(double x){return fabs(x)<eps?0:x<0?-1:1;} bool cmp(P a,P b){double c=(a-p[0])*(b-p[0]);return dcmp(c)?dcmp(c)>0:a.y<b.y;} int n;double ans; void cal(int l,int r) { double x1=0,x2=0;if(l>r)swap(l,r);int i; for(i=l;++i<r;)x1=max(x1,area(p[l],p[r],p[i])); for(i=r;++i<=n;)x2=max(x2,area(p[l],p[r],p[i])); for(i=0;i<l;++i)x2=max(x2,area(p[l],p[r],p[i])); ans=max(ans,x1+x2); } int main() { int i,j; scanf("%d",&n); for(i=j=0;i<n;++i) { scanf("%lf%lf",&p[i].x,&p[i].y); if(p[i].y==p[j].y?p[i].x<p[j].x:p[i].y<p[j].y)j=i; } swap(p[0],p[j]);sort(p+1,p+n,cmp); for(j=1,i=2;i<n;p[++j]=p[i++]) while(j&&dcmp((p[i]-p[j])*(p[j]-p[j-1]))>=0)--j; for(p[n=++j]=p[i=0],j=1;i<n;cal(i,j),cal(++i,j)) while(area(p[i],p[i+1],p[j+1])>area(p[i],p[i+1],p[j]))++j==n?j=0:0; printf("%.3lf",ans/2); }
[BZOJ]1069: [SCOI2007]最大土地面积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。