【BZOJ-1069】最大土地面积 计算几何 + 凸包 + 旋转卡壳

时间：2023-03-08 16:56:22

1069: [SCOI2007]最大土地面积

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit:
2707  Solved: 1053
[Submit][Status][Discuss]

Description

　　在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成
的多边形面积最大。

Input

　　第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。

Output

　　最大的多边形面积，答案精确到小数点后3位。

Sample Input

5
0 0
1 0
1 1
0 1
0.5
0.5

Sample Output

1.000

HINT

数据范围 n<=2000,
|x|,|y|<=100000

Source

Solution

比较裸的一道题，但也有变化之处

比较类似平面最远点对，我们知道所求四边形四个顶点显然存在于凸包上

那么先求一个凸包

那么考虑固定两个点，求以这两点连线为底的第三点分别位于连线上下（左右）的两个三角形，所得到的四边形最大面积

显然对角线可以利用旋转卡壳$O（n）$得到，那么再$O（n）$的枚举另外的第三点，并实时记录答案即可

所以总复杂度为$O（n^{2})$

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int N;

struct Vector

{

    double x,y;

    Vector (double X=,double Y=) {x=X; y=Y;}

};

typedef Vector Point;

#define MAXN 2010

#define eps 1e-8

Point P[MAXN],ch[MAXN];

Vector operator + (Vector A,Vector B) {return (Vector){A.x+B.x,A.y+B.y};}

Vector operator - (Vector A,Vector B) {return (Vector){A.x-B.x,A.y-B.y};}

Vector operator * (Vector A,double p) {return (Vector){A.x*p,A.y*p};}

Vector operator / (Vector A,double p) {return (Vector){A.x/p,A.y/p};}

bool operator < (const Vector& a,const Vector& b) {return a.x<b.x||(a.x==b.x&&a.y<b.y);}

int dcmp(double x) {if (fabs(x)<eps) return ; return x<? -:;}

double Dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}

double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}

double Len(Vector A) {return sqrt(Dot(A,A));}

double DisTL(Point P,Point A,Point B) {Vector v1=B-A,v2=P-A; return fabs(Cross(v1,v2)/Len(v1));}

double Area(Point A,Point B,Point C) {return Cross(B-A,C-A)/;}

int Graham_ConvexHull(Point *p,int num,Point *ch)

{

    sort(p,p+num);

    int k,m=;

    for (int i=; i<=num-; i++)

        {

            while (m> && dcmp(Cross(ch[m-]-ch[m-],p[i]-ch[m-]))<=) m--;

            ch[m++]=p[i];

        }

    k=m;

    for (int i=num-; i>=; i--)

        {

            while (m>k && dcmp(Cross(ch[m-]-ch[m-],p[i]-ch[m-]))<=) m--;

            ch[m++]=p[i];

        }

    if (num>) m--;

    return m;

}

double Triangle_Area(Point A,Point B,int num)

{

    double area1=,area2=;

    for (int i=; i<num; i++)

        area1=max(area1,Area(ch[i],A,B)),

        area2=min(area2,Area(ch[i],A,B));

    return area1+(-area2);

}

double Rotating_Calipers(Point *ch,int num)

{

    if (num== || num==) return ;

    int now=;

    double re=;

    ch[num]=ch[];

    for (int i=; i<num; i++)

        {

            while (dcmp(DisTL(ch[now],ch[i],ch[i+])-DisTL(ch[now+],ch[i],ch[i+]))<)

                now=(now+)%num;

            re=max(re,Triangle_Area(ch[i],ch[now],num));

        }

    return re;

}

int main()

{

    scanf("%d",&N);

    for (int i=; i<N; i++) scanf("%lf%lf",&P[i].x,&P[i].y);

    int m=Graham_ConvexHull(P,N,ch);

    double ans=Rotating_Calipers(ch,m);

    printf("%.3lf\n",ans);

    return ;

}

拿小号交了一下，往删DeBug了WA了一次QAQ结果小号跑得比大号快12MS  T^T

相关文章