POJ 2079 Triangle（凸包_旋转卡壳之最大三角形面积）

题目链接：http://poj.org/problem?id=2079

Description

Input

Output

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

Source

题意：

求最大三角形面积；

PS:

bin神模板！

代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;

struct Point
{
    int x,y;
    Point(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }
    Point operator -(const Point &b)const
    {
        return Point(x - b.x, y - b.y);
    }
    int operator ^(const Point &b)const
    {
        return x*b.y - y*b.x;
    }
    int operator *(const Point &b)const
    {
        return x*b.x + y*b.y;
    }
    void input()
    {
        scanf("%d%d",&x,&y);
    }
};
int dist2(Point a,Point b)
{
    return (a-b)*(a-b);
}
const int MAXN = 50010;
Point list[MAXN];
int Stack[MAXN],top;
bool _cmp(Point p1,Point p2)
{
    int tmp = (p1-list[0])^(p2-list[0]);
    if(tmp > 0)return true;
    else if(tmp == 0 && dist2(p1,list[0]) <= dist2(p2,list[0]))
        return true;
    else return false;
}
void Graham(int n)
{
    Point p0;
    int k = 0;
    p0 = list[0];
    for(int i = 1;i < n;i++)
        if(p0.y > list[i].y || (p0.y == list[i].y && p0.x > list[i].x))
        {
            p0 = list[i];
            k = i;
        }
    swap(list[0],list[k]);
    sort(list+1,list+n,_cmp);
    if(n == 1)
    {
        top = 1;
        Stack[0] = 0;
        return;
    }
    if(n == 2)
    {
        top = 2;
        Stack[0] = 0;
        Stack[1] = 1;
        return;
    }
    Stack[0] = 0;
    Stack[1] = 1;
    top = 2;
    for(int i = 2;i < n;i++)
    {
        while(top > 1 && ((list[Stack[top-1]]-list[Stack[top-2]])^(list[i]-list[Stack[top-2]])) <= 0 )
            top--;
        Stack[top++] = i;
    }
}
//旋转卡壳,求三角形最大面积
int rotating_calipers(Point p[],int n)
{
    int ans = 0;
    Point v;
    int cur = 1;
    for(int i = 0;i < n;i++)
    {
        int j = (i+1)%n;
        int k = (j+1)%n;
        while(j != i && k != i)
        {
            ans = max(ans,abs((p[j]-p[i])^(p[k]-p[i])) );
            while( ( (p[i]-p[j])^(p[(k+1)%n]-p[k]) ) < 0 )
                k = (k+1)%n;
            j = (j+1)%n;
        }
    }
    return ans;
}
Point p[MAXN];
int main()
{
    int n;
    while(scanf("%d",&n) == 1)
    {
        if(n == -1)break;
        for(int i = 0;i < n;i++)
            list[i].input();
        Graham(n);
        for(int i = 0;i < top;i++)
            p[i] = list[Stack[i]];
        int ans = rotating_calipers(p,top);
        printf("%.2lf\n",ans/2.0);
    }
    return 0;
}

POJ 2079 Triangle（凸包_旋转卡壳之最大三角形面积）

原文：http://blog.csdn.net/u012860063/article/details/44628601