サークル(スロープソート+座標系回転)

Problem 2圏地(land.cpp/c/pas)
【タイトル説明】
2次元平面にはn個の杭があり、土を囲む機会があり、土を得ることができます.あなたの高風亮節を体現するために、土の面積をできるだけ小さくしなければなりません.圏地には少なくとも3つの点の多角形を囲む必要があり、多角形の頂点は杭であり、囲まれた土地はこの多角形の内部の土地である.
 
【入力形式】
1行目の整数nは、杭の個数を表す.次にn行、各行2個の整数は1つの杭の座標を表し、座標は2つ異なる.
【出力形式】
1行だけで、最小圏の土地面積を表し、2桁の小数を残す.
【サンプル入力】
サンプル1:3
0 0
0 1
1 0
サンプル2:4
0 0
0 1
0 2
1 1
【サンプル出力】
サンプル1:0.50サンプル2:0.00【データ範囲】
10%のデータに対して、n<=100;30%のデータに対して、n<=300;50%のデータに対して、n<=500;100%のデータに対して、n<=1000.
明らかにこの問題の多角形は三角形に違いない.
まずすべてのエッジを求め、kでソートします(先に求めなければなりません.直接ソートするときに求めることはできません)
そしてこれらのエッジを考えると、ちょうど座標系の周りを一周していることがわかります.
すなわち,こちらをy軸として左から右に並べ替えると,1つのエッジを移すごとに,そのエッジの2点の位置を変えるだけでよい.
この問題は範囲を与えていませんが、long longを使わなければなりません.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN (1000+10)
#define INF (1000000000)
#define eps 1e-10
struct P
{
	int x,y;
	long long operator*(const P &b)
	{
		return (long long)x*b.y-(long long)b.x*y;
	}
	friend bool operator<(P a,P b){if (a.x^b.x)	return a.x<b.x;return a.y<b.y;}
}a[MAXN];
long long abs2(long long x){if (x>0) return x;return -x;}
int n,h[MAXN];
struct E
{
	int i,j;
	double k;
	E(){}
	E(int _i,int _j):i(_i),j(_j){if (a[i].x==a[j].x) k=1e10;else k=(double)(a[i].y-a[j].y)/(a[i].x-a[j].x);}
	friend bool operator<(E a,E b){return a.k<b.k;	}
}e[MAXN*MAXN/2];
long long S2(P A,P B,P C)
{
	return abs2(A*B+B*C+C*A);
}
int size=0;
int main()
{
	freopen("land.in","r",stdin);
	freopen("land.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	long long ans=(long long)1<<60;
	/*	
	for (int i=1;i<=n-2;i++)
		for (int j=i+1;j<n;j++)
			for (int k=j+1;k<=n;k++)
				ans=min(ans,abs2(a[i]*a[j]+a[j]*a[k]+a[k]*a[i]));
	*/
	
	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++) h[i]=i;
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++)
		{
			e[++size]=E(i,j);			
		}
	
	sort(e+1,e+1+size);
	
	for (int i=1;i<=size&&ans;i++)
	{
		if (h[e[i].i]>1&&h[e[i].i]<n) ans=min(ans,S2(a[h[e[i].i]-1],a[h[e[i].i]],a[h[e[i].i]+1]));
		if (h[e[i].j]>1&&h[e[i].j]<n) ans=min(ans,S2(a[h[e[i].j]-1],a[h[e[i].j]],a[h[e[i].j]+1]));
		swap(a[h[e[i].i]],a[h[e[i].j]]);
		swap(h[e[i].i],h[e[i].j]);
	}
	
	printf("%.2lf",(double)ans/2);
	return 0;
}