ACM Note No.20: Geometry

封闭图形面积

int n;
auto work = [&](node a, node b, node c) {
    double x1 = a.x - b.x;
    double y1 = a.y - b.y;

    double x2 = a.x - c.x;
    double y2 = a.y - c.y;

    return (x1 * y2 - x2 * y1) / 2;
};
while (cin >> n) {
    if(n == 0){
        return;
    }
    double ans = 0;
    vector<node> arr(n);
    for (auto &nd : arr) {
        cin >> nd.x >> nd.y;
    }
    for (int i = 1; i < n - 1; i++) {
        ans += work(arr[0], arr[i], arr[i + 1]);
    }
    cout << ans << '\n';
}  

封闭图形重心

int N;
cin >> N;
vector<node> p(N);

for (int i = 0; i < N; ++i) {
cin >> p[i].x >> p[i].y;
}

double s = 0.0;
double x = 0.0, y = 0.0;

for (int i = 0; i < N; ++i) {
    int j = (i + 1) % N;
    double temp = p[i].x * p[j].y - p[j].x * p[i].y;
    s += temp;
    x += (p[i].x + p[j].x) * temp;
    y += (p[i].y + p[j].y) * temp;
}

s *= 0.5;
x /= (6 * s);
y /= (6 * s);

cout << x << " " << y << '\n';

二维凸包

#include<iostream>
#include<algorithm>
#include<stdio.h> 
#include<cmath>
using namespace std;
const int maxn=1e5+10;
struct Node{              //结构体用来存点的信息 
	int x,y;
	double dis,sin_x;
}node[maxn],ans[maxn];   //node存给的点，ans存最终构成凸包的点 
int cnt=0;
int cmp(Node a,Node b){          //按照每个点的坐标排序 
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
void dis(int n){       //计算算每个点与原点的距离及夹角 
	for(int i=1;i<n;i++){
		node[i].dis=(double)sqrt(pow(node[i].x-node[0].x,2)+pow(node[i].y-node[0].y,2));
		node[i].sin_x=(double)(node[i].y-node[0].y)/node[i].dis;
	}
}
int cmp1(Node a,Node b){       //对角度和到原点的距离排序 
	if(a.sin_x==b.sin_x) return a.dis<b.dis;
	return a.sin_x<b.sin_x;
}
bool judge(int ni){            //判断这个点是不是凸包上的点 
	if(cnt<2) return true;
	Node a=ans[cnt-1];
	Node b=ans[cnt-2];
	Node c=node[ni];
	if((c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y)<=0) return false;
	else return true;
}
void lang(){
	double sum=0;
	for(int i=1;i<cnt;i++){      //计算距离 
		sum+=(double)sqrt(pow(ans[i].x-ans[i-1].x,2)+pow(ans[i].y-ans[i-1].y,2));
	}
	//如果只有两个点，则不需要计算最后一个点和第0个点的距离 
	if(cnt>2) sum+=(double)sqrt(pow(ans[0].x-ans[cnt-1].x,2)+pow(ans[0].y-ans[cnt-1].y,2));
	printf("%.2lf\n",sum);
}
int main(){
	int n;
	while(scanf("%d",&n)){
		if(n==0) break;
		cnt=0;
		for(int i=0;i<n;i++) scanf("%d%d",&node[i].x,&node[i].y);
		if(n==1){            //如果只有一个点，不需要绳子围住 
			printf("0.00\n");
			continue;
		}
		sort(node,node+n,cmp);     //对点排序，找到最下边的那个点 
		
		node[0].dis=0;
		node[0].sin_x=-1;
		dis(n);
		sort(node,node+n,cmp1);
		
		ans[cnt++]=node[0];      //前两个点一定是凸包上的点 
		ans[cnt++]=node[1];
		for(int i=2;i<n;i++){
			while(!judge(i)) cnt--;     //找这个点在凸包的位置 
			ans[cnt++]=node[i];
		}
		lang();    //计算距离 
	}	
	return 0;
}