bzoj 1069

 

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

 

/**************************************************************Problem: 1069User: idy002Language: C++Result: AcceptedTime:232 msMemory: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)) > 0;
}
int convex( int n, Point *p, Point *c ) {int m;sort( p, p+n );c[m=0] = p[0];for( int i=1; i<n; i++ ) {while( m>0 && !onleft(c[m-1],c[m],p[i]) ) m--;c[++m] = p[i];}int k=m;for( int i=n-2; i>=0; i-- ) {while( m>k && !onleft(c[m-1],c[m],p[i]) ) m--;c[++m] = p[i];}return m+(n==1);
}
double area( Point &A, Point &B, Point &P ) {return (B-A)^(P-A);
}
double maxarea( int n, Point *p ) {if( n<=2 ) return 0.0;if( n==3 ) return fabs(area(p[0],p[1],p[2]));static int nxt[N];nxt[n-1]=0;for( int i=0; i<n-1; i++ ) nxt[i]=i+1;double rt = 0.0;for( int i=0; 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=0; i<n; i++ ) scanf( "%lf%lf", &pts[i].x, &pts[i].y );cn = convex( n, pts, cvx );printf( "%.3lf\n", maxarea(cn,cvx) );
}