注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1069: [SCOI2007]最大土地面积(旋转卡壳+凸包)  

2014-05-21 13:47:00|  分类: oi,bzoj,凸包,旋 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目: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 ; 

}



  评论这张
 
阅读(62)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018