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;
}

原文地址：https://blog.csdn.net/2302_79277225/article/details/143697621

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！