首页 > ACM题库 > HDU-杭电 > HDU 4097-Triangles and Quadrangle-计算几何-[解题报告]HOJ
2015
04-16

HDU 4097-Triangles and Quadrangle-计算几何-[解题报告]HOJ

Triangles and Quadrangle

问题描述 :

  Little Yuan is two years old and she is learning about some triangles and quadrangles. She is such a smart girl that she soon realizes two triangles can form a quadrangle without overlapping each other. She picks up a lot of triangles and uses them to form some quadrangles. Unfortunately, she is not good at this kind of jigsaw game and makes some mistakes.
  As her brother, you are curious about whether she has made a mistake when forming two triangles into a quadrangle. You are thinking about to write a program to determine it.
  Notice that the quadrangle in this problem is defined as a simple polygon with four vertexes. And you may also assume that all triangles and quadrangle have positive area.
  Note that two graphs are considered as the same if and only if they can overlap completely by shifting, rotation and flipping. You can also shifting, rotation and flipping one of the triangles to form the triangles to a quadrangle.

输入:

  There are multiple test cases. The first line of input contains a single integer T denoting the number of test cases. (T <= 500)
  For each test case, there are 10 lines in total.
  The first 3*2 lines describe the two triangles. Each line with two integers denotes the coordinates of a point.
  The next 4 lines describe the quadrangle in clockwise order or counter-clockwise order.
  All coordinates are less than 15000 in absolute value.

输出:

  There are multiple test cases. The first line of input contains a single integer T denoting the number of test cases. (T <= 500)
  For each test case, there are 10 lines in total.
  The first 3*2 lines describe the two triangles. Each line with two integers denotes the coordinates of a point.
  The next 4 lines describe the quadrangle in clockwise order or counter-clockwise order.
  All coordinates are less than 15000 in absolute value.

样例输入:

2
0 0
0 1
1 0
0 0
0 1
1 0
-1 0
0 0
1 0
0 1
0 0
-1 1
1 0
0 0
0 1
1 0
-1 0
0 0
1 0
0 1

样例输出:

Case #1: Yes
Case #2: No

今天做了11年的上海区域赛, 比赛的时候贡献一道简单的几何,WA了2次才找到 漏了一个情况, 结果4WA后AC。

题意:给你2个三角形和一个多边形(可能凹,可能退化成三角型,点按逆时针或顺时针给出)。

比赛的时候少了"可能退化成三角型"的情况。发现问题后改了一会后AC。

退化成三角型的处理方法:


先去掉多边形中多余的那个点(共线的三个点的中间点)。

然后把2个三角形拼接成一个三角形,最后判2个三角形是否全等。

拼接过程:枚举2个三角形的公共边,然后枚举所有拼接情况(拼接的边和公共边之间2个夹角之和为180)。

具体看代码吧:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const double eps = 1e-8;
const double pi = acos(-1.0);
int dcmp(double x) {
	if(fabs(x) < eps)
		return 0;
	return x > eps ? 1 : -1;
}
struct point {
	double x, y;
	point(double x = 0, double y = 0) :
			x(x), y(y) {
	}
	point operator-(const point &t) const {
		return point(x - t.x, y - t.y);
	}
	point operator*(const double &t) const {
		return point(x * t, y * t);
	}
	void in() {
		scanf("%lf%lf", &x, &y);
	}
} p[4];
double dis(point a, point b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double angle(double a, double b, double c) {
	return acos((b * b + c * c - a * a) / (2 * b * c));
}
struct tri {
	point p[3];
	double d[3], jiao[3];   //边,边所对的角
	//边从小到大排序
	void in() {
		int i;
		for(i = 0; i < 3; i++)
			p[i].in();
		for(i = 0; i < 3; i++)
			d[i] = dis(p[i], p[(i + 1) % 3]);
		sort(d, d + 3);
		for(i = 0; i < 3; i++)
			jiao[i] = angle(d[i], d[(i + 1) % 3], d[(i + 2) % 3]);
	}
} t1, t2;

double cross(point a, point b) {
	return a.x * b.y - a.y * b.x;
}
bool judge(int x, int y, int a, int b) {
	//可能出现凹多边形
	//判点x和y所连的线是否能把多边形切成2个三角形
	int f1 = dcmp(cross(p[y] - p[x], p[a] - p[x]));
	int f2 = dcmp(cross(p[y] - p[x], p[b] - p[x]));
	if(!f1 || !f2)
		return 0;
	if(f1 != f2)
		return 1;
	return 0;
}

bool equal(point a, point b, point c, tri t) {
	point p[3];
	double d[3];
	p[0] = a;
	p[1] = b;
	p[2] = c;
	int i;
	for(i = 0; i < 3; i++)
		d[i] = dis(p[i], p[(i + 1) % 3]);
	sort(d, d + 3);
	for(i = 0; i < 3; i++)
		if(d[i] != t.d[i])
			return 0;
	return 1;
}
bool Cao(double a, double b, double c, double *dd) {
	double d[4];
	d[0] = a;
	d[1] = b;
	d[2] = c;
	sort(d, d + 3);
	for(int i = 0; i < 3; i++)
		if(dcmp(d[i] - dd[i]))
			return 0;
	return 1;
}
typedef pair <double, double> pii;
int main() {
	int i, j, cas, ca = 1;
	scanf("%d", &cas);
	while(cas--) {
		t1.in();
		t2.in();
		for(i = 0; i < 4; i++)
			p[i].in();
		printf("Case #%d: ", ca++);
		bool ok = 0;
		if(judge(0, 2, 1, 3)) {
			if(!ok && equal(p[0], p[1], p[2], t1)
					&& equal(p[0], p[3], p[2], t2))
				ok = 1;
			if(!ok && equal(p[0], p[1], p[2], t2)
					&& equal(p[0], p[3], p[2], t1))
				ok = 1;

		}
		if(judge(1, 3, 0, 2)) {
			if(!ok && equal(p[1], p[0], p[3], t1)
					&& equal(p[1], p[2], p[3], t2))
				ok = 1;
			if(!ok && equal(p[1], p[0], p[3], t2)
					&& equal(p[1], p[2], p[3], t1))
				ok = 1;
		}
		if(!ok) {
			int i, j, k;
			point q[4];
			int pos = -1;
			for(i = 0; i < 4; i++)
				if(!dcmp(
						cross(p[i] - p[(i + 2) % 4],
								p[(i + 1) % 4] - p[(i + 2) % 4]))) {
					pos = (i + 1) % 4; //找出多边形共线中要去掉的那个点
					break;
				}

			loop: int tot = 0;
			if(pos != -1) {
				for(i = 0; i < 4; i++)
					if(i != pos) {
						q[tot++] = p[i];
					}
				for(i = 0; i < 3; i++)
					p[i] = q[i];

				double area1 = fabs(cross(t1.p[0] - t1.p[1], t1.p[0] - t1.p[2]))
						+ fabs(cross(t2.p[0] - t2.p[1], t2.p[0] - t2.p[2]));
				double area2 = fabs(cross(p[0] - p[1], p[2] - p[1]));
				if(!dcmp(area1 - area2)) {
					double dd[4]; //退化后的多边形(三角形)的三条边的长度
					for(i = 0; i < 3; i++)
						dd[i] = dis(p[i], p[(i + 1) % 3]);
					sort(dd, dd + 3);
					for(i = 0; i < 3; i++)
						for(j = 0; j < 3; j++)
							if(!dcmp(t1.d[i] - t2.d[j])) {	//枚举两个三角形的公共边
								int x, y;
								vector <pii> la, lb;
								for(x = 0; x < 3; x++)
									if(x != i)
										la.push_back(
												make_pair(t1.d[x], t1.jiao[x]));
								for(x = 0; x < 3; x++)
									if(x != j)
										lb.push_back(
												make_pair(t2.d[x], t2.jiao[x]));

								for(x = 0; x < 2; x++)     //2个三角形剩下的边拼接起来判是否合法
									for(y = 0; y < 2; y++) {
										if(!dcmp(la[x].second + lb[y].second- pi)
												&& Cao(la[x].first, lb[y].first, la[x ^ 1].first + lb[y ^ 1].first, dd))
											ok = 1;
									}
							}
				}
			}
		}
		if(ok)
			puts("Yes");
		else
			puts("No");
	}
	return 0;
}
/*
 -3 0
 -2 0
 0 3
 -2 0
 3 0
 0 3
 -3 0
 0 0
 3 0
 0 3
 */

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/auto_ac/article/details/12317601


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c