凸包旋转卡壳求最大三角形面积

最大三角形

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3316 Accepted Submission(s): 1119

Problem Description 老师在计算几何这门课上给Eddy布置了一道题目，题目是这样的：给定二维的平面上n个不同的点，要求在这些点里寻找三个点，使他们构成的三角形拥有的面积最大。
Eddy对这道题目百思不得其解，想不通用什么方法来解决，因此他找到了聪明的你，请你帮他解决这个题目。
Input 输入数据包含多组测试用例，每个测试用例的第一行包含一个整数n，表示一共有n个互不相同的点，接下来的n行每行包含2个整数xi,yi，表示平面上第i个点的x与y坐标。你可以认为：3 <= n <= 50000 而且 -10000 <= xi, yi <= 10000.
Output 对于每一组测试数据，请输出构成的最大的三角形的面积，结果保留两位小数。
每组输出占一行。

Sample Input

Sample Output

1.50
27.00

Author Eddy

/* ***********************************************
Author        :CKboss
Created Time  :2014年12月28日 星期日 19时28分15秒
File Name     :HDOJ2202.cpp
************************************************ */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             using namespace std; struct Point { double x,y; Point operator - (Point a) const { return (Point){x-a.x,y-a.y}; } bool operator < (Point a) const { if(x!=a.x) return x
             
               vp; vector
              
                ch; void CovexHull(vector
               
                 &p) { sort(p.begin(),p.end()); p.erase(unique(p.begin(),p.end()),p.end()); int n=p.size(); m=0; ch=vector
                
                 (n+1); for(int i=0;i
                 
                  1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--; ch[m++]=p[i]; } int k=m; for(int i=n-2;i>=0;i--) { while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--; ch[m++]=p[i]; } if(n>1) m--; ch.resize(m); } double Rotating_Calipers(vector
                  
                   & p,int n) { double ans=0; for(int i=0;i

HDOJ 2202 最大三角形 凸包旋转卡壳求最大三角形面积

最大三角形

HDOJ 2202 最大三角形凸包旋转卡壳求最大三角形面积