POJ 2079(计算几何+凸包+旋转卡壳法)

太过爱你忘了你带给我的痛 2022-06-08 11:23 311阅读 0赞

问题描述:

Given n distinct points on a plane, your task is to find the triangle that have the maximum area, whose vertices are from the given points.

Input

The input consists of several test cases. The first line of each test case contains an integer n, indicating the number of points on the plane. Each of the following n lines contains two integer xi and yi, indicating the ith points. The last line of the input is an integer −1, indicating the end of input, which should not be processed. You may assume that 1 <= n <= 50000 and −10 4 <= xi, yi <= 10 4 for all i = 1 . . . n.

Output

For each test case, print a line containing the maximum area, which contains two digits after the decimal point. You may assume that there is always an answer which is greater than zero.

Sample Input

3
    3 4
    2 6
    2 7
    5
    2 6
    3 9
    2 0
    8 0
    6 5
    -1

Sample Output

0.50
    27.00

题目题意:题目给了我们n个点，问这n个点中三个点能构成三角形最大面积是多少?

题目分析:我们以这n个点构成一个二维凸包，那么这三个点一定在上面，因为它们是最外面的点，现在就是在这个凸包上找到三个点求最大面积。

挑战设计竞赛上有种方法叫旋转卡壳法。

假定有 p q,r 三个点，我们先固定p,q,去求出使得三角形面积最大的点r,然后固定p,r，求出最大面积时的q,p就是遍历凸包所有的点

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    
    const int MAXN=50000+500;
    struct point
    {
        int x,y;
    };
    point list[MAXN];//凸包的点
    int stack[MAXN],top;//stack保存的是最后凸包的点的序号
    
    double cross(point p0,point p1,point p2) //计算叉积  p0p1 X p0p2
    {
        return (double ) (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
    }
    double dis(point p1,point p2)  //计算 p1p2的 距离
    {
        return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
    }
    bool cmp(point p1,point p2) //极角排序函数 ， 角度相同则距离小的在前面
    {
        int tmp=cross(list[0],p1,p2);
        if(tmp>0) return true;
        else if(tmp==0&&dis(list[0],p1)<dis(list[0],p2)) return true;
        else return false;
    }
    void init(int n) //输入，并把  最左下方的点放在 list[0]  。并且进行极角排序
    {
        int i,k;
        point p0;
        scanf("%d%d",&list[0].x,&list[0].y);
        p0.x=list[0].x;
        p0.y=list[0].y;
        k=0;
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&list[i].x,&list[i].y);
            if( (p0.y>list[i].y) || ((p0.y==list[i].y)&&(p0.x>list[i].x)) )
            {
                p0.x=list[i].x;
                p0.y=list[i].y;
                k=i;
            }
        }
        list[k]=list[0];
        list[0]=p0;
    
        sort(list+1,list+n,cmp);
    }
    
    void graham(int n)
    {
        int i;
        if(n==1) {top=0;stack[0]=0;}
        if(n==2)
        {
            top=1;
            stack[0]=0;
            stack[1]=1;
        }
        if(n>2)
        {
            for(i=0;i<=1;i++) stack[i]=i;
            top=1;
    
            for(i=2;i<n;i++)
            {
                while(top>0&&cross(list[stack[top-1]],list[stack[top]],list[i])<=0) top--;
                top++;
                stack[top]=i;
            }
        }
    }
    int main()
    {
        int n;
        while (scanf("%d",&n)!=EOF) {
            if (n==-1) break;
            init(n);
            graham(n);
            double ans=0;
            int p=1,q=2;
            stack[++top]=stack[0];
            for (int i=0;i<top;i++) {
                while (cross(list[stack[i]],list[stack[p]],list[stack[q+1]])>cross(list[stack[i]],list[stack[p]],list[stack[q]]))
                    q=(q+1)%top;
                ans=max(ans,fabs(cross(list[stack[i]],list[stack[p]],list[stack[q]]))/2.0);
                while (cross(list[stack[i]],list[stack[p+1]],list[stack[q]])>cross(list[stack[i]],list[stack[p]],list[stack[q]]))
                    p=(p+1)%top;
                ans=max(ans,fabs(cross(list[stack[i]],list[stack[p]],list[stack[q]]))/2.0);
            }
            printf("%.2f\n",ans);
        }
        return 0;
    }