bzoj1069 [SCOI2007]最大土地面积旋转卡壳

2022-07-12 16:49:36

1069: [SCOI2007]最大土地面积

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 3767 Solved: 1501
[Submit][Status][Discuss]

Description

　　在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成
的多边形面积最大。

Input

　　第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。

Output

　　最大的多边形面积，答案精确到小数点后3位。

Sample Input

5
0 0
1 0
1 1
0 1
0.5 0.5

Sample Output

1.000

HINT

数据范围 n<=2000, |x|,|y|<=100000

先求凸包，然后n^2枚举对角线，用旋转卡壳去找位于对角线两侧且到对角线距离最大的两点构成2个三角形，2个三角形面积和就是四边形面积

 #include<bits/stdc++.h>

 #define N 2010

 using namespace std;

 int n,tp;

 struct P{

     double x,y;

     bool operator < (const P &b)const{

         return x==b.x?y<b.y:x<b.x;

     }

     P operator - (const P &b)const{

         return (P){x-b.x,y-b.y};

     }

 }a[N],s[N];

 double crs(P a,P b){return a.x*b.y-a.y*b.x;}

 void getbag(){

     sort(a+,a++n);

     for(int i=;i<=n;i++){

         while(tp>&&crs(a[i]-s[tp-],s[tp]-s[tp-])>=)--tp;

         s[++tp]=a[i];

     }

     int now=tp;

     for(int i=n-;i>=;i--){

         while(tp>now&&crs(a[i]-s[tp-],s[tp]-s[tp-])>=)--tp;

         s[++tp]=a[i];

     }

     if(n>)--tp;

 }

 void getans(){

     double ans=;s[tp+]=s[];

     for(int i=;i<=tp-;i++){

         int a=i+,b=(i+)%tp+;

         for(int j=i+;j<=tp;j++){

             while(a%tp+!=j&&crs(s[a]-s[i],s[j]-s[i])<crs(s[a+]-s[i],s[j]-s[i]))a=a%tp+;

             while(b%tp+!=i&&crs(s[j]-s[i],s[b]-s[i])<crs(s[j]-s[i],s[b+]-s[i]))b=b%tp+;

             ans=max(ans,(crs(s[a]-s[i],s[j]-s[i])+crs(s[j]-s[i],s[b]-s[i]))/);

         }

     }

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

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     scanf("%lf%lf",&a[i].x,&a[i].y);

     getbag();getans();

     return ;

 }

码农公寓