欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

相关标签: swust 计算几何