BZOJ 1069 [SCOI2007] 最大土地面积

Description

　　在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。

Input

　　第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。

Output

　　最大的多边形面积，答案精确到小数点后3位。

Sample Input

Sample Output

HINT

数据范围 n<=2000, |x|,|y|<=100000

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

旋转卡壳~

好棒的算法啊！

n<=2000，所以枚举对角线，然后分别在两边求出最大面积三角型，更新答案即可，其中枚举对角线ij后，在两边分别取两个点，while循环寻找最大面积的顶点，因为这个顶点的面积具有单调性，所以在j循环中不用每次新设xy，这里用到了旋转卡壳，复杂度不高~

（给的样例真是水，我原来那份到处是错的代码都能过样例……）

有几个注意点：

1.都是double型；

2.叉积小心先后顺序；

3.xy是先取模后+1，否则会超出范围；

4.事实证明，数组开大一点是好习惯。

#include<cstdio>#include<iostream>#include<algorithm>using namespace std;int n,tot;struct node{	double x,y;}a[2005],c[2005];double dis(node u,node v){	return (u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y);}node Operator -(node u,node v){	node p;	p.x=u.x-v.x;p.y=u.y-v.y;	return p;}double operator *(node u,node v){	return u.x*v.y-u.y*v.x;}bool operator <(node u,node v){	double k=(u-a[1])*(v-a[1]);	if(k==0) return dis(u,a[1])<dis(v,a[1]);	return k<0;}void chan(){	int min=1;	for(int i=2;i<=n;i++)	  if(a[min].y>a[i].y || (a[min].y==a[i].y && a[min].x>a[i].x)) min=i;	swap(a[min],a[1]);	sort(a+2,a+n+1);	c[++tot]=a[1];c[++tot]=a[2];	for(int i=3;i<=n;i++)	{		while(tot>1 && (a[i]-c[tot-1])*(c[tot]-c[tot-1])<=0) tot--;		c[++tot]=a[i];	}}double cal(){	double ans=0;c[tot+1]=c[1];	for(int i=1;i<=tot-2;i++)	{		int x=i%tot+1,y=(i+2)%tot+1;		for(int j=i+2;j<=tot;j++)		{			while(x%tot+1!=j && (c[j]-c[i])*(c[x+1]-c[i])>(c[j]-c[i])*(c[x]-c[i])) x=x%tot+1;			while(y%tot+1!=i && (c[y+1]-c[i])*(c[j]-c[i])>(c[y]-c[i])*(c[j]-c[i])) y=y%tot+1;			ans=max(ans,(c[j]-c[i])*(c[x]-c[i])+(c[y]-c[i])*(c[j]-c[i]));		}	}	return ans;}int main(){	scanf("%d",&n);	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);	chan();	PRintf("%.3lf/n",cal()/2);	return 0;}