题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1632

题目大意

给定两个可能相互重叠的凸多边形。如果存在重叠,其重叠的角度和方向各异。你要写一个程序读入两个凸多边形各角点的坐标,并计算出二者“异或”得到的区域的面积,也就是在二者全部区域中仅存在其中一个多边形的区域。

题解

用半平面交求出两个凸多边形的重叠部分,然后利用叉积公式 Sigma(x[i+1]*y[i] - y[i+1]*x[i]) 求出三个凸包的面积,用题目给定的两个凸包面积减去两倍重叠部分面积就是答案。

知识点

半平面, 顾名思义,半平面就是指平面的一半。我们知道,一条直线可以将平面分为两个部分,那么这两个部分就叫做两个半平面。二维坐标系下,直线可以表示为ax + by + c = 0,那么两个半平面则可以表示为ax + by + c >= 0 和ax + by + c < 0,这就是半平面的表示方法。 

半平面其实就是一个方程组,让你画出满足若干个式子的坐标系上的区域(类似于线性规划的可行域),方程组就是由类似于上面的这些不等式组成的。 半平面交虽然说是半平面的问题,但它其实就是关于直线的问题。一个一个的半平面其实就是一个一个有方向的直线而已。 

半平面交的一个重要应用就是求多边形的核。它是平面简单多边形的核是该多边形内部的一个点集,该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。就是一个在一个房子里面放一个摄像头,能将所有的地方监视到的放摄像头的地点的集合即为多边形的核。经常会遇到让你判定一个多边形是否有核的问题。

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 100;
const double eps = 1e-8;
struct point {
	double x, y;
	point() {}
	point(double _x, double _y): x(_x), y(_y) {}
	void input() {
		scanf("%lf%lf", &x, &y);
	}
};
point A[N + 5], B[N + 5], C[N + 5], p[N + 5], q[N + 5];

double cross(point x, point y) {
	return x.x*y.y - x.y*y.x;
}

int sgn(double x) {
	if (x > eps) return 1;
	if (x < -eps) return -1;
	return 0;
}

int initial(point T[], int n) {
	for (int i = 1; i <= n; ++i) p[i] = T[i];
	p[0] = p[n], p[n + 1] = p[1];
	return n;
}

void getline(point x, point y, double &a, double &b, double &c) {
	a = y.y - x.y;
	b = x.x - y.x;
	c = y.x*x.y - x.x*y.y;
	return;
}

point intersect(point x, point y, double a, double b, double c) {
	double u = fabs(a*x.x + b*x.y + c);
	double v = fabs(a*y.x + b*y.y + c);
	return point((x.x*v + y.x*u)/(u + v), (x.y*v + y.y*u)/(u + v));
}

int cut(int cnt, point X, point Y) {
	double a, b, c;
	getline(X, Y, a, b, c);
	int cur = 0;
	for (int i = 1; i <= cnt; ++i)
		if (sgn(a*p[i].x + b*p[i].y + c) >= 0) q[++cur] = p[i];
		else {
            if(sgn(a*p[i - 1].x + b*p[i - 1].y + c) > 0) q[++cur] = intersect(p[i], p[i - 1], a, b, c);
            if(sgn(a*p[i + 1].x + b*p[i + 1].y + c) > 0) q[++cur] = intersect(p[i], p[i + 1], a, b, c);
		}
	for (int i = 1; i <= cur; ++i) p[i] = q[i];
	p[0] = q[cur], p[cur + 1] = q[1];
	return cur;
}

double calcArea(point T[], int n) {
	double res = 0.0;
	for (int i = 1; i <= n; ++i) res += cross(T[i], T[(i % n) + 1]);
	return fabs(res/2.0);
}

void solve(int n, int m) {
	int cnt = initial(A, n);
	for (int i = 1; i <= m; ++i)
		cnt = cut(cnt, B[i], B[(i % m) + 1]);
	//for (int i = 1; i <= cnt; ++i) printf("%lf %lf\n", p[i].x, p[i].y); //for debug
	double ans = calcArea(A, n) + calcArea(B, m) - calcArea(p, cnt)*2.0;
	//printf("%lf %lf %lf\n", calcArea(A, n), calcArea(B, m), calcArea(p, cnt)); //for debug
	printf("%8.2lf", ans);
	return;
}

int main() {
	int n;
	while (scanf("%d", &n) && n) {
		for (int i = 1; i <= n; ++i) scanf("%lf%lf", &A[i].x, &A[i].y);
		int m;
		scanf("%d", &m);
		for (int i = 1; i <= m; ++i) scanf("%lf%lf", &B[i].x, &B[i].y);
		solve(n, m);
	}
	printf("\n");
	return 0;
}
转载保留版权:http://haipz.com/blog/i/6022 - 海胖博客