1069: [SCOI2007]最大土地面积

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 3998  

Solved: 1620

[ ][ ][ ]

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

Source

 

[ ][ ][ ]

首先我们可以考虑到如果我们取到了一个最大的四边形，那么这个四边形的四个顶点一定是这些点凸包上的点。也就是说，我们需要先求出这些点的凸包。

那么求出来了之后呢？我们很明显不能暴力求。。。复杂度明显是N^4级别。那么我们应该怎么求呢？考虑四边形性质，可以沿着对角线分成两个三角形，我们只需枚举对角线即可，然后旋转卡壳，求出两边最大三角形的面积求和即可。三角形的面积可以是这个三角形构成平行四边形的面积/2，所以用叉积就可以方便求出。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define inf 50000000#define re register#define MAXN 5005using namespace std;struct node{ double x,y;};node a[MAXN],stackk[MAXN];double xx,yy;int n,top;inline int read(){ int x=0,c=1; char ch=' '; while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); while(ch=='-') c*=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar(); return x*c;}inline bool cmp(node a,node b){ if(a.y==b.y) return a.x
           
            0) return 1; else if(k==0) return js(stackk[1],a)
            
             0&&cross(stackk[top-1],stackk[top],a[i])<=0) top--; stackk[++top]=a[i]; } stackk[++top]=a[1]; double ans=0; int a,b; for(re int x=1;x<=top;x++){ a=x%top+1;b=(x+2)%top+1; for(re int y=x+2;y<=top;y++){ while(a%top+1!=y&&cross(stackk[x],stackk[a+1],stackk[y])>cross(stackk[x],stackk[a],stackk[y])) a=a%top+1; while(b%top+1!=x&&cross(stackk[x],stackk[y],stackk[b+1])>cross(stackk[x],stackk[y],stackk[b])) b=b%top+1; ans=max(cross(stackk[x],stackk[a],stackk[y])+cross(stackk[x],stackk[y],stackk[b]),ans); } } printf("%.3lf",ans/2);}