Largest Triangle （凸包+旋转卡壳求最大三角形）

题意：在二维坐标中给出(n)个点，在这些点中挑(3)个点能组成的面积最大的三角形的面积
AC_Code:
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <string>
 5 #include <algorithm>
 6 #include <cstring>
 7 using namespace std;
 8 typedef long long ll;
 9 const int maxn = 5e4+10;
10 const double eps = 1e-8;
11 
12 
13 typedef struct Point{
14     double x,y;
15     Point(double x=0,double y=0):x(x),y(y){}
16 }Vector;
17 
18 Vector operator + (const Vector &A, const Vector &B){ return Vector(A.x+B.x,A.y+B.y); }
19 Vector operator - (const Vector &A, const Vector &B){ return Vector(A.x-B.x,A.y-B.y); }
20 Vector operator * (const Vector &A, double p){ return Vector(A.x*p,A.y*p); }
21 Vector operator / (const Vector &A, double p){ return Vector(A.x/p,A.y/p); }
22 
23 bool operator <(const Point &A,const Point &B){
24     return A.x<B.x || (A.x==B.x && A.y<B.y);
25 }
26 
27 int dcmp(double x){
28     if( fabs(x)<eps ) return 0;
29     return x<0 ? -1 : 1;
30 }
31 
32 double Cross(const Vector &A, const Vector &B){
33     return A.x*B.y-A.y*B.x;
34 }
35 
36 double Dot(const Vector &A, const Vector &B){
37     return A.x*B.x+A.y*B.y;
38 }
39 
40 double Length(const Vector &A){
41     return Dot(A,A);
42 }
43 
44 double Area2(const Point &A, const Point &B, const Point &C){
45     return Cross(B-A,C-A);
46 }
47 
48 int ConvexHull(Point *p,int n,Point *ch){
49     sort(p,p+n);
50     int m=0;
51     for(int i=0;i<n;i++){
52         while( m>1 && dcmp(Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0 ) m--;
53         ch[m++]=p[i];
54     }
55     int k=m;
56     for(int i=n-2;i>=0;i--){
57         while( m>k && dcmp(Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0) m--;
58         ch[m++]=p[i];
59     }
60     if( n>1 ) m--;
61     return m;
62 }
63 
64 Point p[maxn],ans[maxn];
65 
66 double RotatingCaliper(int m, Point *ch){
67     if( m<=2 ) return 0;
68     if( m==3 ) return fabs( Cross(ch[1]-ch[0], ch[2]-ch[0]) )*0.5;
69     double ans = 0.0;
70     int i,j,k;
71     for(i=0;i<m;i++){
72         j=(i+1)%m; k=(j+1)%m;
73         while( fabs( Area2(ch[i],ch[j],ch[k]) ) < fabs( Area2(ch[i],ch[j],ch[(k+1)%m]) ) ) k=(k+1)%m;
74 
75         while( i!=j && k!=i ){
76             ans = max(ans, fabs( Area2(ch[i],ch[j],ch[k]) ));
77             while( fabs( Area2(ch[i],ch[j],ch[k]) ) < fabs( Area2(ch[i],ch[j],ch[(k+1)%m]) ) ) k=(k+1)%m;
78             j=(j+1)%m;
79         }
80     }
81     return ans*0.5;
82 }
83 
84 int main()
85 {
86     int n;
87     while( ~scanf("%d",&n) ){
88         for(int i=0;i<n;i++){
89             double x,y; scanf("%lf%lf",&x,&y);
90             p[i] = Point(x,y);
91         }
92         int cnt = ConvexHull(p,n,ans);
93         double res = RotatingCaliper(cnt,ans);
94         printf("%.7f
",res);
95     }
96     return 0;
97 }