POJ 2079 Triangle （凸包+旋转卡壳）

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

【题目大意】

　　给出一些点，求出能组成的最大面积的三角形

【题解】

　　最大三角形一定位于凸包上，因此我们先求凸包，再在凸包上计算，
　　因为三角形在枚举了一条固定边之后，图形面积随着另一个点的位置变换先变大后变小
　　因此我们发现面积递减之后就移动固定边。

【代码】

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

double EPS=1e-10;

const double PI=acos(-1.0);

double add(double a,double b){

    if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;

    return a+b;

}

struct P{

    double x,y;

    P(){}

    P(double x,double y):x(x),y(y){}

    P operator + (P p){return P(add(x,p.x),add(y,p.y));}

    P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}

    P operator * (double d){return P(x*d,y*d);}

    double dot(P p){return add(x*p.x,y*p.y);} //点积

    double det(P p){return add(x*p.y,-y*p.x);}  //叉积

};

bool cmp_x(const P& p,const P& q){

    if(p.x!=q.x)return p.x<q.x;

    return p.y<q.y;

}

vector<P> convex_hull(P* ps,int n){

    sort(ps,ps+n,cmp_x);

    int k=0;

    vector<P> qs(n*2);

    for(int i=0;i<n;i++){

        while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;

        qs[k++]=ps[i];

    }

    for(int i=n-2,t=k;i>=0;i--){

        while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;

        qs[k++]=ps[i];

    }qs.resize(k-1);

    return qs;

}

double cross(P A,P B,P C){return(B-A).det(C-A);}

const int MAX_N=50010;

int N;

P ps[MAX_N];

void solve(){

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

    vector<P> qs=convex_hull(ps,N);

    N=qs.size(); int ans=0;

    for(int i=1;i<(N+1)/2;i++){ //枚举跨度

        int p1=(i+1)%N;

        for(int p3=0;p3<N;p3++){

            int p2=(p3+i)%N;

            int prev=abs(cross(qs[p3],qs[p2],qs[p1]));

            for(++p1;p1!=p2&&p1!=p3;++p1){

                if(p1==N)p1=0;

                int cur=abs(cross(qs[p3],qs[p2],qs[p1]));

                ans=max(ans,prev);

                if(cur<=prev)break;

                prev=cur;

            }--p1;

            if(p1==-1)p1+=N;

        }

    }printf("%d.%s\n",ans/2,ans%2==1?"50":"00");

}

int main(){

    while(~scanf("%d",&N)&&N>0)solve();

    return 0;

}