【NOI六连测】[D3T2] 最大土地面积

题目传送门:http://pan.baidu.com/s/1nvKqStz
离线版题目:http://paste.ubuntu.com/18378190/
数据传送门:http://pan.baidu.com/s/1skSFZxr

哎呀,本来想着终于可以A题了!结果又被卡常QAQ,然后又只有60分QAQ
正解就是凸包+旋转卡壳+乱搞,然而原教的代码完全没有几何库,全部写进代码%%%%%%%,因此他天生自带小常数啊!
原教 Orz:http://paste.ubuntu.com/18378298/
哎呀,不想卡常了,贴一份代码水过就算了吧

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

const int MAXN = 8000+9;
const double EPS = 1e-8;
const double INF = 1e30;

double vout;
int n;

inline int cmp(double x){if (fabs(x)<EPS) return 0; else return (x>0)?1:-1;}

struct Point{
	double x,y;
	inline bool operator < (const Point &A) const {return (x < A.x) || (x == A.x && y < A.y);} inline bool operator == (const Point &A) const {return !cmp(x-A.x) && !cmp(y-A.y);} inline Point operator + (const Point &A) {Point tmp;tmp.x=x+A.x;tmp.y=y+A.y;return tmp;} inline Point operator - (const Point &A) {Point tmp;tmp.x=x-A.x;tmp.y=y-A.y;return tmp;} }p[MAXN],TMP[MAXN],ori[MAXN],SIZE[MAXN]; typedef Point Vector; inline double Cross(Vector A, Vector B){return A.x*B.y - A.y*B.x;} inline double Area2(Point A, Point B, Point C){return Cross(B-A, C-A);} inline bool Onleft(Point A, Point B, Point C){return cmp(Area2(A,B,C)) > 0;}

inline void CalArea(Point *A){
	A[5] = A[1]; double ret = 0;
	for (int i=1;i<=4;i++)
		ret += Cross(A[i],A[i+1]);
	vout = max(vout, fabs(ret));
}

inline int ConvexHull(Point *A, int N){
	sort(A+1,A+1+N); int cnt=0;
	
	for (int i=1;i<=N;i++){ while (cnt > 1 && !Onleft(TMP[cnt-1],TMP[cnt],A[i])) cnt--;
		TMP[++cnt] = A[i];
	} for (int i=N-1,lim=cnt;i;i--){
		while (cnt > lim && !Onleft(TMP[cnt-1],TMP[cnt],A[i])) cnt--;
		TMP[++cnt] = A[i];
	}	
	
	if (cnt==4 && N==4) {
		for (int i=1,tag;i<=4;i++){
			tag = 0;
			for (int j=1;j<cnt;j++)
				if (A[i] == TMP[j]) tag = 1;
			if (!tag) {A[4]=A[i];break;}
		}
	} for (int i=1;i<cnt;i++) A[i] = TMP[i];
	return cnt-1;
}

inline void update(Point *A){
	if (ConvexHull(A,4) == 4) CalArea(A);
	else {
		double sa = fabs(Area2(A[1],A[2],A[3]));
		double mn = INF; A[5] = A[4]; A[4] = A[1];
		for (int i=1;i<=3;i++) mn = min(mn, fabs(Area2(A[i],A[i+1],A[5])));
		if (vout < sa-mn) vout = max(vout, sa-mn);
	}
}

inline void cycle(int N){
	for (int i=1;i<=N;i++) p[i+N] = p[i];
	for (int i=1;i<=N;i++) p[i+N*2] = p[i];
	for (int k=2;k<N;k++){
		for (int i=1,itr1=2,itr2=i+k+1;i<=N;i++){
			while (itr1 < i+k && fabs(Area2(p[i],p[itr1],p[i+k])) <= fabs(Area2(p[i],p[itr1+1],p[i+k]))) itr1++;
			while (itr2 < i+N && fabs(Area2(p[i+k],p[itr2],p[i])) <= fabs(Area2(p[i+k],p[itr2+1],p[i]))) itr2++;
			SIZE[1] = p[i]; SIZE[2] = p[itr1]; SIZE[3] = p[i+k]; SIZE[4] = p[itr2];
			CalArea(SIZE);
		}
	}
}

int main(){
	freopen("large.in","r",stdin);
	freopen("large.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) 
		scanf("%lf%lf",&p[i].x,&p[i].y),
		ori[i] = p[i];
	int tmp = ConvexHull(p,n);
	if (tmp == 4) CalArea(p);
	else if (tmp == 3) for (int i=1;i<=n;i++){
		int t = 1;
		for (int j=1;j<=3;j++) 
			if (p[j]==ori[i]) t=0;
		if (t) p[4] = ori[i], update(p);
	} else cycle(tmp);
	printf("%.3lf",vout/2.0);
	return 0;
}

唯一比较欣慰的,快4个月没有写过几何题了,居然还能写出来,还没怎么调试就过了。