HDOJ 2202最大三角形の凸包は回転して殻を押さえて最大三角形の面積を求めます

凸包の回転の殻は最大の三角形の面積を求めます
最大三角形
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に1つのテーマを配置して、テーマはこのようにします:2次元の平面の上でnつの異なる点を与えて、これらの点の中で3つの点を探して、彼らの構成する三角形の持つ面積を最大にすることを要求します.
Eddyはこの問題について何も考えていないので、どんな方法で解決するか分からないので、彼は頭のいいあなたを見つけました.この問題を解決してください.
 
Input
入力データには複数の試験例が含まれ、各試験例の最初の行には整数nが含まれ、合計n個の互いに異なる点があることを示し、次のn行には2個の整数xi,yiが含まれ、平面上のi番目の点のxとy座標を表す.3<=n<=50000および-1000<=xi,yi<=10000と考えることができます.
 
Output
各テストデータのセットについて、構成された最大三角形の面積を出力し、結果は2桁の小数を保持します.
出力のグループごとに1行を占めます.
 
Sample Input

   
   
   
   

    
    
    
    3
3 4
2 6
3 7
6
2 6
3 9
2 0
8 0
6 6
7 7
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1.50
27.00
   
   
   
   

 
Author
Eddy
 

/* ***********************************************
Author        :CKboss
Created Time  :2014 12 28      19 28 15 
File Name     :HDOJ2202.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

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<a.x;
		return y<a.y;
	}
	bool operator == (Point a) const
	{
		return (x==a.x)&&(y==a.y);
	}
};

int n,m;

double Cross(Point A,Point B) { return A.x*B.y-A.y*B.x; }

double Area2(const Point A,const Point B,const Point C)
{
	return fabs(Cross(B-A,C-A));
}

vector<Point> vp;
vector<Point> ch;

void CovexHull(vector<Point> &p)
{
	sort(p.begin(),p.end());
	p.erase(unique(p.begin(),p.end()),p.end());
	int n=p.size();
	m=0;
	ch=vector<Point>(n+1);
	for(int i=0;i<n;i++)
	{
		while(m>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<Point>& p,int n)
{
	double ans=0;
	for(int i=0;i<n;i++)
	{
		int j=(i+1)%n;
		int k=(j+1)%n;
		while(j!=i&&k!=i)
		{
			ans=max(ans,Area2(p[i],p[j],p[k]));
			while(Cross(p[i]-p[j],p[(k+1)%n]-p[k])<0)
				k=(k+1)%n;
			j=(j+1)%n;
		}
	}
	return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	while(scanf("%d",&n)!=EOF)
	{
		vp.clear();
		for(int i=0;i<n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			vp.push_back((Point){x,y});
		}
		CovexHull(vp);
		double area=Rotating_Calipers(ch,ch.size())/2.;
		printf("%.2lf
",area);
	}

    return 0;
}