BZOJ-1069: [SCOI2007]最大土地面积（旋转卡壳

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1069

先做出凸包，然后顺时针枚举对角线，我们就发现四边形的另外两个相对的点在顺时针方向上是递增的，于是乎就O( n^2 )可以AC了。。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

 

using namespace std ;

 

#define rep( i , l , r ) for ( int i = l ; i <= r ; ++ i )

 

const double esp = 1e-8 ;

const int maxn = 2010 ;

 

struct Point {

    double x , y ;

    void read(  ) {

        scanf( "%lf%lf" , &x , &y ) ;

    }

    void print(  ) {

        printf( "( %.2f , %.2f )\n" , x , y ) ;

    }

} ;

 

struct Vector {

    double x , y ;

} ;

 

double operator * ( const Vector &x , const Vector &y ) {

    return x.x * y.y - y.x * x.y ;

}

 

Vector operator - ( const Point &x , const Point &y ) {

    return ( Vector ) { x.x - y.x , x.y - y.y } ;

}

 

double cmp( double x , double y ) {

    return ( x - y ) < - esp ? -1 : ( x - y ) > esp ;

}

 

bool cmp0( Point x , Point y ) {

    return cmp( x.y , y.y ) == 1 || ( ! cmp( x.y , y.y ) && cmp( x.x , y.x ) == - 1 ) ;

}

 

bool cmp1( Point x , Point y ) {

    return cmp( x.y , y.y ) == - 1 || ( ! cmp( x.y , y.y ) && cmp( x.x , y.x ) == 1 ) ;

}

 

Point p[ maxn ] , P[ maxn ] ;

int n , m = 0 ;

 

Point S[ maxn ] ;

int Top ;

 

double cal( Point a , Point b , Point c ) {

    return abs( ( ( a - c ) * ( b - c ) ) ) / 2.0 ;

}

 

int main(  ) {

    scanf( "%d" , &n ) ;

    rep( i , 1 , n ) p[ i ].read(  ) ;

    sort( p + 1 , p + n + 1 , cmp0 ) ;

    Top = 0 ;

    rep( i , 1 , n ) {

        while ( Top > 1 ) if ( cmp( ( S[ Top ] - S[ Top - 1 ] ) * ( p[ i ] - S[ Top - 1 ] ) , 0 ) != - 1 ) -- Top ; else break ;

        S[ ++ Top ] = p[ i ] ;

    }

    rep( i , 1 , Top ) P[ ++ m ] = S[ i ] ;

    sort( p + 1 , p + n + 1 , cmp1 ) ;

    Top = 0 ;

    rep( i , 1 , n ) {

        while ( Top > 1 ) if ( cmp( ( S[ Top ] - S[ Top - 1 ] ) * ( p[ i ] - S[ Top - 1 ] ) , 0 ) != - 1 ) -- Top ; else break ;

        S[ ++ Top ] = p[ i ] ;

    }

    rep( i , 2 , Top - 1 ) P[ ++ m ] = S[ i ] ;

    rep( i , 1 , m )  P[ m + i ] = P[ i ] ;

    double ans = 0 ;

    rep( i , 1 , m ) {

        int l = i + 1 , r = i + 3 ;

        rep( j , i + 2 , m ) {

            for ( ; cal( P[ i ] , P[ j ] , P[ l ] ) <= cal( P[ i ] , P[ j ] , P[ l + 1 ] ) ; ++ l ) ;

            for ( ; cal( P[ i ] , P[ j ] , P[ r ] ) <= cal( P[ i ] , P[ j ] , P[ r + 1 ] ) ; ++ r ) ;

            ans = max( ans , cal( P[ i ] , P[ j ] , P[ l ] ) + cal( P[ i ] , P[ j ] , P[ r ] ) ) ;

        }

    }

    printf( "%.3f\n" , ans ) ;

    return 0 ; 

}