bzoj 1069

最开始想到的是枚举3个点，另一个点用卡壳的思想，但实际上可以只枚举两个点（对角线上的两个点），其余两个点用卡壳。

/**************************************************************

    Problem: 1069

    User: idy002

    Language: C++

    Result: Accepted

    Time:232 ms

    Memory:880 kb

****************************************************************/

#include <cstdio>

#include <cmath>

#include <algorithm>

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

#define eps 1e-10

#define N 2010

using namespace std;

int sg( double x ) { return (x>-eps)-(x<eps); }

struct Vector {

    double x, y;

    Vector(){}

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

    Vector operator+( const Vector & b ) const { return Vector(x+b.x,y+b.y); }

    Vector operator-( const Vector & b ) const { return Vector(x-b.x,y-b.y); }

    Vector operator*( double b ) const { return Vector(x*b,y*b); }

    Vector operator/( double b ) const { return Vector(x/b,y/b); }

    double operator^( const Vector & b ) const { return x*b.y-y*b.x; }

    double operator&( const Vector & b ) const { return x*b.x+y*b.x; }

    bool operator<( const Vector & b ) const {

        return x<b.x || (x-b.x<eps && y<b.y);

    }

};

typedef Vector Point;

bool onleft( Point &A, Point &B, Point &P ) {

    return sg((B-A)^(P-A)) > ;

}

int convex( int n, Point *p, Point *c ) {

    int m;

    sort( p, p+n );

    c[m=] = p[];

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

        while( m> && !onleft(c[m-],c[m],p[i]) ) m--;

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

    }

    int k=m;

    for( int i=n-; i>=; i-- ) {

        while( m>k && !onleft(c[m-],c[m],p[i]) ) m--;

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

    }

    return m+(n==);

}

double area( Point &A, Point &B, Point &P ) {

    return (B-A)^(P-A);

}

double maxarea( int n, Point *p ) {

    if( n<= ) return 0.0;

    if( n== ) return fabs(area(p[],p[],p[]));

    static int nxt[N];

    nxt[n-]=;

    for( int i=; i<n-; i++ ) nxt[i]=i+;

    double rt = 0.0;

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

        for( int j=nxt[nxt[i]],a=nxt[i],b=nxt[j]; nxt[j]!=i; j=nxt[j] ) {

            while( area(p[i],p[a],p[j])<area(p[i],p[nxt[a]],p[j]) ) a=nxt[a];

            while( area(p[j],p[b],p[i])<area(p[j],p[nxt[b]],p[i]) ) b=nxt[b];

            double ra = area(p[i],p[a],p[j]);

            double rb = area(p[j],p[b],p[i]);

            rt = max( rt, ra+rb );

        }

    }

    return rt/2.0;

}

int n, cn;

Point pts[N], cvx[N];

int main() {

    scanf( "%d", &n );

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

        scanf( "%lf%lf", &pts[i].x, &pts[i].y );

    cn = convex( n, pts, cvx );

    printf( "%.3lf\n", maxarea(cn,cvx) );

}