swust OJ 249 求凸包面积模板
程序员文章站
2022-03-18 10:54:29
用Graham_scan 求出凸点,再用叉积求面积,一个三角形的面积等于叉积的一半。#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#include#define int long longusing namespace std;typedef pair pii;typedef long long ll;const int INF = 0x3f...
用Graham_scan 求出凸点,再用叉积求面积,一个三角形的面积等于叉积的一半。
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double eps = 1e-5;
const int mod = 2013;
const int N = 1e5+10;
int n;
struct Point{
int x,y;
}point[N];
// 叉积 求 ab x ac -> >0 c在 b 左
int cross(Point a,Point b,Point c){
int x1 = b.x - a.x,y1 = b.y - a.y;
int x2 = c.x - a.x,y2 = c.y - a.y;
return x1*y2 - x2*y1;
}
#define C(x) ((x)*(x))
int dis(Point a,Point b){
return C(a.x - b.x) + C(a.y - b.y);
}
bool cmp(Point a,Point b){
int t = cross(point[0],a,b);
return t?t>0:dis(point[0],a) > dis(point[0],b);
}
//进行处理,用栈来存元素,当有有拐趋势,则出栈。
int stk[N],top = -1;
void Graham_scan(){
stk[++top] = 0;
stk[++top] = 1;
stk[++top] = 2;
for(int i=3;i<n;i++){
while(cross(point[stk[top-1]],point[stk[top]],point[i]) <= 0)
--top;
stk[++top] = i;
}
}
signed main(){
IOS
#ifdef ddgo
freopen("C:\\Users\\asus\\Desktop\\ddgoin.txt","r",stdin);
#endif
int tt; cin>>tt;
while(tt --){
cin>>n;
top = -1;
for(int i=0;i<n;i++){
cin>>point[i].x>>point[i].y;
if(i){
if(point[i].y == point[0].y && point[i].x < point[0].x)
swap(point[0],point[i]);
else if(point[i].y < point[0].y) swap(point[0],point[i]);
}
}
if(n < 3){
cout<<"0.0"<<endl;
continue;
}
sort(point+1,point+n,cmp);
int cnt = 2;
for (int i=2;i<n;i++)
if(cross(point[0],point[i-1],point[i]) != 0) point[cnt++] = point[i];
n = cnt;
Graham_scan();
double res = 0;
for(int i=2;i<=top;i++)
res += cross(point[0],point[stk[i-1]],point[stk[i]]);
cout<<fixed<<setprecision(1)<<(res/2)<<endl;
}
return 0;
}
本文地址:https://blog.csdn.net/qq_45604735/article/details/109616280
上一篇: 利用Gradle发布项目到JCenter