249: 凸包面积

解法：

使用Andrew算法【计算几何/凸包】安德鲁算法（Andrew's Algorithm）详解_andrew算法求凸包-CSDN博客

1. 排序：

   • 将所有点按照x坐标进行升序排序。如果x坐标相同，则按照y坐标升序排序。

2. 初始化栈：

   • 使用一个栈（或数组）s来存储凸包上的点，初始时为空。

3. 构建下凸包：

   • 从左至右遍历排序后的点集。
   • 对于每个点，检查栈顶的两个点和当前点是否构成逆时针方向的转向（即叉积是否为正）。
   • 如果不构成逆时针方向，从栈中弹出栈顶点，直到栈顶只剩下两个点或者当前点与栈顶两个点构成逆时针方向。
   • 将当前点压入栈。

4. 构建上凸包：

   • 从右至左遍历排序后的点集。
   • 类似于构建下凸包的过程，检查栈顶的两个点和当前点是否构成逆时针方向的转向。
   • 如果不构成逆时针方向，从栈中弹出栈顶点，直到栈顶只剩下两个点或者当前点与栈顶两个点构成逆时针方向。
   • 将当前点压入栈。

5. 合并凸包：

   • 由于下凸包和上凸包在最左端点和最右端点处重叠，需要去除重复的点。
   • 合并下凸包和上凸包（除去重叠部分）得到完整的凸包。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e3;
struct P{
	int x,y;
}p[N];
int n;
bool cmp(P a,P b){
	if (a.x!=b.x){
		return a.x<b.x;
	}else{
		return a.y<b.y;
	}
}
double cross(P o,P a,P b){
	return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
void Andrew(){
	sort(p,p+n,cmp);
	vector<P> s;
	for (int i=0;i<n;i++){
		while (s.size()>=2&&cross(s[s.size()-2],s[s.size()-1],p[i])<=0){
			s.pop_back();
		}
		s.push_back(p[i]);
	}
	int t=s.size();
	for (int i=n-1;i>=0;i--){
		while (s.size()>=1+t&&cross(s[s.size()-2],s[s.size()-1],p[i])<=0){
			s.pop_back();
		}
		s.push_back(p[i]);
	}
	double area=0;
	for (int i=0;i<s.size()-2;i++){
		area+=cross(s[0],s[i],s[i+1]);
	}
	printf("%.1lf\n",abs(area)/2);
}
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n;
		for (int i=0;i<n;i++){
			cin>>p[i].x>>p[i].y;
		}
		Andrew();
	}
	return 0;
}