[旋转卡壳]最大土地面积 AcWing2617

[旋转卡壳]最大土地面积 AcWing2617

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

输入格式

第 1 行一个正整数 N。

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

输出格式

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

数据范围

4≤N≤2000,
|x|,|y|≤105

输入样例：

5
0 0
1 0
1 1
0 1
0.5 0.5

输出样例：

1.000

题意： 题意比较清晰，就是在点集中找四个点构成一个面积最大的四边形。

分析： 要找的四个点一定出现在凸包顶点上，证明在旋转卡壳算法总结里面，直接暴力枚举四个顶点显然是不可取的，但是可以枚举四边形的对角线，当对角线确定了后再找到距离对角线最远的两点就构成了在这条对角线的前提下最大的四边形，这个过程就可以通过旋转卡壳来实现，具体代码上其实和Triangle POJ2079这道题比较相似，不过这道题要用两个变量分别记录两侧的最远点。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 101000;
//`Compares a double to zero`
int sgn(double x)
{
	if(fabs(x) < eps)return 0;
	if(x < 0)return -1;
	else return 1;
}
//square of a double
inline double sqr(double x){return x*x;}

struct Point
{
	double x, y;
	Point(){}
	Point(double _x,double _y){x = _x, y = _y;}
	void input(){scanf("%lf%lf",&x,&y);}
	void output(){printf("%.2f %.2fn",x,y);}
	bool operator == (Point b)const{return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;}
	bool operator < (Point b)const{return sgn(x-b.x)== 0?sgn(y-b.y)<0:x 0;
		}
	};
	//`进行极角排序`
	//`首先需要找到最左下角的点`
	//`需要重载号好Point的 < 操作符(min函数要用) `
	void norm(){
		Point mi = p[0];
		for(int i = 1;i < n;i++)mi = min(mi,p[i]);
		sort(p,p+n,cmp(mi));
	}
	//`得到凸包`
	//`得到的凸包里面的点编号是0$sim$n-1的`
	//`两种凸包的方法`
	//`注意如果有影响，要特判下所有点共点，或者共线的特殊情况`
	//`测试 LightOJ1203  LightOJ1239`
	void getconvex(polygon &convex){
		sort(p,p+n);
		convex.n = n;
		for(int i = 0;i < min(n,2);i++){
			convex.p[i] = p[i];
		}
		if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
		if(n <= 2)return;
		int &top = convex.n;
		top = 1;
		for(int i = 2;i < n;i++){
			while(top && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
				top--;
			convex.p[++top] = p[i];
		}
		int temp = top;
		convex.p[++top] = p[n-2];
		for(int i = n-3;i >= 0;i--){
			while(top != temp && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
				top--;
			convex.p[++top] = p[i];
		}
		if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
		convex.norm();//`原来得到的是顺时针的点，排序后逆时针`
	}
	//`得到凸包的另外一种方法`
	//`测试 LightOJ1203  LightOJ1239`
	//如果要保留所有共线点需要极角排序后最后一条边上的点逆序处理且出栈条件去掉等号
	//去掉等号后需要保证不存在重复点，否则会出错 
	//更改一下最后一条边的排序顺序 
	//	int k;
	//	for(k = a.n-1; k >= 0; k--)
	//		if(sgn((a.p[k]-a.p[0])^(a.p[k-1]-a.p[0])) != 0)
	//			break; 
	//	reverse(a.p+k, a.p+a.n); 
	void Graham(polygon &convex){
		norm();
		int &top = convex.n;
		top = 0;
		if(n == 1){
			top = 1;
			convex.p[0] = p[0];
			return;
		}
		if(n == 2){
			top = 2;
			convex.p[0] = p[0];
			convex.p[1] = p[1];
			if(convex.p[0] == convex.p[1])top--;
			return;
		}
		convex.p[0] = p[0];
		convex.p[1] = p[1];
		top = 2;
		for(int i = 2;i < n;i++){
			while( top > 1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2])) <= 0 )
				top--;
			convex.p[top++] = p[i];
		}
		if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
	}
	//`判断是不是凸的`
	bool isconvex(){
		bool s[3];
		memset(s,false,sizeof(s));
		for(int i = 0;i < n;i++){
			int j = (i+1)%n;
			int k = (j+1)%n;
			s[sgn((p[j]-p[i])^(p[k]-p[i]))+1] = true;
			if(s[0] && s[2])return false;
		}
		return true;
	}
	//`得到周长`，点要相邻 
	//`测试 LightOJ1239`
	double getcircumference(){
		double sum = 0;
		for(int i = 0;i < n;i++)
			sum += p[i].distance(p[(i+1)%n]);
		return sum;
	}
	//`得到面积`，点要相邻 
	double getarea()
	{
		double sum = 0;
		for(int i = 0;i < n;i++)
			sum += (p[i]^p[(i+1)%n]);
		return fabs(sum)/2;
	}
	//`判断点和任意多边形的关系`
	//` 3 点上`
	//` 2 边上`
	//` 1 内部`
	//` 0 外部`
	int relationpoint(Point q){
		for(int i = 0;i < n;i++){
			if(p[i] == q)return 3;
		}
		getline();
		for(int i = 0;i < n;i++){
			if(l[i].pointonseg(q))return 2;
		}
		int cnt = 0;
		for(int i = 0;i < n;i++){//图形学上的内外测试 
			int j = (i+1)%n;
			int k = sgn((q-p[j])^(p[i]-p[j]));//向右侧引一条射线 
			int u = sgn(p[i].y-q.y);
			int v = sgn(p[j].y-q.y);
			if(k > 0 && u < 0 && v >= 0)cnt++;//向量两点y值小的被截断一部分 
			if(k < 0 && v < 0 && u >= 0)cnt--;
		}
		return cnt != 0;
	}
};

polygon a, con; 

signed main()
{
	int n;
	cin >> n;
	a.input(n);
	a.Graham(con);
	a = con;
	for(int i = 0; i < con.n; i++)
		a.add(con.p[i]);
	double ans = 0.0;
	//枚举对角线 
	for(int i = 0; i < con.n; i++)
	{
		for(int j = i+2, k1 = i+1, k2 = j+1; j < i+con.n-1; j++)
		{
			while(((a.p[i]-a.p[j])^(a.p[k1]-a.p[i])) < ((a.p[i]-a.p[j])^(a.p[k1+1]-a.p[i])))
				k1++;
			while(((a.p[j]-a.p[i])^(a.p[k2]-a.p[i])) < ((a.p[j]-a.p[i])^(a.p[k2+1]-a.p[i])))
				k2++;
			ans = max(ans, ((a.p[i]-a.p[j])^(a.p[k1]-a.p[i]))+((a.p[j]-a.p[i])^(a.p[k2]-a.p[i])));
		}
	}
	printf("%.3fn", ans/2);
	return 0;
}