最开始想到的是枚举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) );
}
05-26 13:03