Who's Studio.

hihoCoder#1040 - 矩形判断

Word count: 366Reading time: 2 min
2016/05/12

题目

给出平面上4条线段，判断这4条线段是否恰好围成一个面积大于0的矩形。
具体描述请见hihoCoder。

解题思路

死条线段能够围成矩形的充要条件为：任意两条线段若相交必垂直，且相交次数恰好为4。

时间复杂度

时间复杂度为1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
using namespace std;

bool intersect(int* line1, int* line2) {
	return ((line1[0] == line2[0] && line1[1] == line2[1]) ||
		(line1[0] == line2[2] && line1[1] == line2[3]) ||
		(line1[2] == line2[0] && line1[3] == line2[1]) ||
		(line1[2] == line2[2] && line1[3] == line2[3]));
}

bool isVertical(int* line1, int* line2) {
	int x1 = line1[2] - line1[0];
	int y1 = line1[3] - line1[1];
	int x2 = line2[2] - line2[0];
	int y2 = line2[3] - line2[1];

	return (x1 * x2 + y1 * y2) == 0;
}

bool isPoint(int* line) {
	return (line[0] == line[2] && line[1] == line[3]);
}

bool checkRec(int** coord) {
	for (int i = 0; i < 4; i++)
		if (isPoint(coord[i]))
			return false;

	int count = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = i + 1; j < 4; j++) {
			if (intersect(coord[i], coord[j])) {
				if (isVertical(coord[i], coord[j]))
					count++;
				else
					return false;
			}
		}
	}
	if (count == 4)
		return true;

	return false;
}

int main() {
	int T = 0;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int** coord = new int*[4];
		for (int i = 0; i < 4; i++)
			coord[i] = new int[4];
		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 4; j++)
				cin >> coord[i][j];

		cout << (checkRec(coord) ? "YES" : "NO") << endl;

		for (int i = 0; i < 4; i++)
			delete[] coord[i];
		delete[] coord;
	}

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/12/2016-05-12-hihocoder-rectangle-check/

Publish date：May 12th 2016, 8:03:25 pm

Update date：December 4th 2022, 5:06:16 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目