旋转卡壳入门三——POJ 2079 Triangle

我会带着你远行 2022-05-24 05:12 194阅读 0赞

[Triangle][]  
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个平面上的顶点，求这些顶点可构成的最大三角形面积。这里需要用到求凸包算法+旋转卡壳，挺好的一道练手题，虽然自己被卡了好多天!!!

直接贴AC代码吧  
看不懂的可以先去学习一波graham求凸包算法再看！！！

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    const int N = 50005;
    struct Point{
        int x,y;
    }p[N],Stack[N];
    int n;
    
    int mult(Point a,Point b,Point c){
        return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
    }
    int dis(Point a,Point b){
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    }
    int cmp(Point a,Point b){
        if(mult(a,b,p[0])>0) return 1;
        if(mult(a,b,p[0])==0&&dis(b,p[0])>dis(a,p[0])) return 1;
        return 0;
    }
    int Graham(){
        //找到最左下角的点，作为起始点 
        int k = 0;
        for(int i=1;i<n;i++){
            if(p[k].y>p[i].y||(p[k].y==p[i].y)&&(p[k].x>p[i].x)){
                k=i;
            }
        }
        swap(p[0],p[k]);
        // 按极角从小到大，距离从小到大排序 
        sort(p+1,p+n,cmp);
        //开始扫描，求出凸包顶点 
        int top = 2;
        Stack[0]=p[0];
        Stack[1]=p[1];
        Stack[2]=p[2];
        for(int i=3;i<n;i++){
            while(top>=1&&mult(p[i],Stack[top],Stack[top-1])>=0){
                top--;
            }
            Stack[++top]=p[i];
        }
        return top;
    }
    double rotating_calipers(int top){
       int p=1,q=2; ///初始化
       double ans = 0;
       Stack[++top]=Stack[0];
       for(int i = 0;i<top;i++){
            while(mult(Stack[i],Stack[p],Stack[q+1])>mult(Stack[i],Stack[p],Stack[q])){
                q= (q+1)%top; ///定点i,p,q,先I,p固定,让q旋转找到最大的面积三角形,还是利用了凸包的单峰函数
            }
            ans = max(ans,mult(Stack[i],Stack[p],Stack[q])/2.0);
            while(mult(Stack[i],Stack[p+1],Stack[q])>mult(Stack[i],Stack[p],Stack[q])){
                p=(p+1)%top; ///i,q固定,p旋转,找到最大的三角形面积,比较记录.
            }
            ans = max(ans,mult(Stack[i],Stack[p],Stack[q])/2.0);
       }
       return ans;
    }
    int main()
    {
        while(scanf("%d",&n)!=EOF,n!=-1){
            for(int i=0;i<n;i++){
                scanf("%d%d",&p[i].x,&p[i].y);
            } 
            int top = Graham();
            double ans =rotating_calipers(top);
            printf("%.2f\n",ans);
        }
        return 0;
    }

[Triangle]: https://vjudge.net/contest/214418#problem/C