Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 3177  Solved: 1255

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

 

数学问题 计算几何 凸包 旋转卡壳

要找四个点围成最大面积，显然这四个点应该在凸包上。

所以先求出凸包来。

之后当然不能四重循环枚举选点。

可以枚举选其中的两个点，假装作辅助线把凸包分成两半，在两半中各自找一个面积最大的三角形，三角形顶点就是使得选中面积最大的点。

对于一条边而言，凸包上的点到这条边的距离是满足单峰性质的，所以可以开两个指针单调扫过去。

这似乎就是传说中的旋转卡壳？

 

迷之WA，（一边肝菲特狗一边）对拍半天就是找不出错。

最后静态查错试着把33行的>0改成>=0就过了

简直要气哭

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 const double eps=1e-8; 9 const int mxn=3010;10 struct Point{11 double x,y;12 }a[mxn];13 Point operator + (Point L,Point r){ return (Point){L.x+r.x,L.y+r.y};}14 Point operator - (Point L,Point r){ return (Point){L.x-r.x,L.y-r.y};}15 inline double Cross(Point a,Point b){ return a.x*b.y-a.y*b.x;}16 inline double dist(Point a,Point b){17 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));18 }19 int n;20 int st[mxn],top=0;21 int Pcmp(Point x,Point y){22 double res=Cross(x-a[1],y-a[1]);23 if(abs(res)<=eps)return dist(x,a[1])
           
            0;25 }26 void HAM(){27 int p=1,i;28 for(i=2;i<=n;i++)29 if(a[i].x
            
             a[p].y)) p=i;30 swap(a[1],a[p]);31 sort(a+2,a+n+1,Pcmp);32 for(i=1;i<=n;i++){33 while(top>1 && Cross(a[i]-a[st[top-1]],a[st[top]]-a[st[top-1]])>=0)top--;34 st[++top]=i;35 }36 return;37 }38 void solve(){39 HAM();40 st[top+1]=1;41 double ans=0;42 int hd,tl,i,j;43 for(i=1;i<=top;i++){44 hd=i%top+1;tl=(i+2)%top+1;45 for(j=i+2;j<=top;j++){46 Point tmp=a[st[j]]-a[st[i]];47 while(tl%top+1!=i && Cross(tmp,a[st[tl+1]]-a[st[i]])>Cross(tmp,a[st[tl]]-a[st[i]]))48 tl=tl%top+1;49 while(hd%top+1!=j && Cross(a[st[hd+1]]-a[st[i]],tmp)>Cross(a[st[hd]]-a[st[i]],tmp))50 hd=hd%top+1;51 ans=max(ans,Cross(tmp,a[st[tl]]-a[st[i]])+Cross(a[st[hd]]-a[st[i]],tmp));52 }53 }54 printf("%.3lf",ans/2);55 return;56 }57 int main(){58 // freopen("in.txt","r",stdin);59 // freopen("out1.txt","w",stdout);60 int i,j;61 scanf("%d",&n);62 for(i=1;i<=n;i++)63 scanf("%lf%lf",&a[i].x,&a[i].y);64 solve();65 return 0;66 }