在某块平面土地上有N个点,你可以选择其中的任意四个点,将这片土地围起来,当然,你希望这四个点围成的多边形面积最大。
数据范围 n<=2000, |x|,|y|<=100000
输入格式:
第1行一个正整数N,接下来N行,每行2个数x,y,表示该点的横坐标和纵坐标。
输出格式:
最大的多边形面积,答案精确到小数点后3位。
直接讲做法吧
很容易脑补出来,如果要面积最大,四边形的顶点一定都在凸包上
(不要问me凸包只有三个点的情况…me也不是很清楚,不过貌似没有这样的数据)
用单调栈维护出凸包之后,在凸包上枚举两个点的连线作为四边形的对角线,然后在对角线两边分别找面积最大三角形
很明显在固定两个点之后,另外两个点也是有单调性的,时间复杂度
关于最大四边形四点一定在凸包上的正确性,如果有一个点在凸包内,那么< 对角线-当前顶点 >三角形的面积一定是比< 对角线-凸包顶点 >三角形的面积小的,画个图就会明白了
#include#include #include #include using namespace std ; const double eps = 1e-13 ; int N , topp ; struct Vector{ double x , y ; Vector(){} ; Vector( double x_ , double y_ ): x(x_) , y(y_){} ; double len(){ return sqrt( x * x + y * y ) ; } } ; typedef Vector Point ; Point a[2005] , poly[2005] ; int dcmp( double x ){ if( x < eps && x > -eps ) return 0 ; return x > eps ? 1 : -1 ; } Vector operator + ( const Vector &A , const Vector &B ) { return Vector( A.x+B.x , A.y+B.y ) ; } Vector operator - ( const Vector &A , const Vector &B ) { return Vector( A.x-B.x , A.y-B.y ) ; } Vector operator * ( const Vector &A , const double &p ) { return Vector( A.x*p , A.y*p ) ; } Vector operator / ( const Vector &A , const double &p ) { return Vector( A.x/p , A.y/p ) ; } bool operator == ( const Vector &A , const Vector &B ) { return ( A.x == B.x && A.y == B.y ); } bool operator < ( const Point &A , const Point &B ) { return A.x < B.x || ( A.x == B.x && A.y < B.y ) ; } double fabs ( double x ){ return dcmp(x) < 0 ? -x : x ; } double Dot ( const Vector &A , const Vector &B ){ return A.x * B.x + A.y * B.y ; } double Cross( const Vector &A , const Vector &B ){ return A.x * B.y - A.y * B.x ; } void convex( Point *a , int siz , Point *p , int &topp ){ sort( a + 1 , a + siz + 1 ) ; topp = 0 ; for( int i = 1 ; i <= siz ; i ++ ){ while( topp >= 2 && Cross( a[i] - p[topp-1] , p[topp] - p[topp-1] ) >= 0 ) topp -- ; p[++topp] = a[i] ; } int las = topp ; for( int i = siz - 1 ; i >= 1 ; i -- ){ while( topp - las >= 1 && Cross( a[i] - p[topp-1] , p[topp] - p[topp-1] ) >= 0 ) topp -- ; p[++topp] = a[i] ; } topp -- ; /* for( int i = 1 ; i <= topp ; i ++ ){ printf( "poly : [%f %f]\n" , p[i].x , p[i].y ) ; } */ } double ans ; void RC(){ poly[topp+1] = poly[1] ; for( int i = 1 ; i <= topp ; i ++ ){ int dn = i+1 , up = (i+2)%topp+1 ; for( int j = i + 2 ; j <= topp ; j ++ ){ while( fabs( Cross( poly[dn] - poly[i] , poly[j] - poly[i] ) ) < fabs( Cross( poly[dn+1] - poly[i] , poly[j] - poly[i] ) ) ) dn ++ ; while( fabs( Cross( poly[j] - poly[i] , poly[up] - poly[i] ) ) < fabs( Cross( poly[j] - poly[i] , poly[up+1] - poly[i] ) ) ) up = up %topp + 1 ; ans = max( ans , fabs( Cross( poly[up] - poly[i] , poly[j] - poly[i] ) ) + fabs( Cross( poly[j] - poly[i] , poly[dn] - poly[i] ) ) ) ; } } printf( "%.3f" , ans/2 ) ; } int main(){ scanf( "%d" , &N ) ; for( int i = 1 ; i <= N ; i ++ ) scanf( "%lf%lf" , &a[i].x , &a[i].y ) ; convex( a , N , poly , topp ) ; RC() ; }