hihoCoder#1040 矩形判断

一开始写了一个求交点然后算角度的，特别复杂不说，还很容易出错，WA了很久也不知道错在哪

后来想想，应该用向量做

四条直线能围成一个矩形 <=> 四条直线两两之间有4个平行关系，8个垂直关系

注意，直线重合并不算平行

代码清晰明了，一遍AC，这酸爽。

代码：

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 struct Line {
 7   int x[2];
 8   int y[2];
 9   Line(int x1, int y1, int x2, int y2) {
10     x[0] = x1;
11     x[1] = x2;
12     y[0] = y1;
13     y[1] = y2;
14   }
15   int vx() {return x[0] - x[1];}
16   int vy() {return y[0] - y[1];}
17 };
18 
19 bool parallelp(Line &a, Line &b) {
20   return a.vx() * b.vy() - b.vx() * a.vy() == 0;
21 }
22 
23 bool samep(Line &a, Line &b) {
24   Line c(a.x[0], a.y[0], b.x[0], b.y[0]);
25   return parallelp(a, c);
26 }
27 
28 bool verticalp(Line &a, Line &b) {
29   return a.vx() * b.vx() + a.vy() * b.vy() == 0;
30 }
31 
32 int parallel_count(vector<Line> &lines) {
33   int res = 0;
34 
35   for (int i = 0; i < 4; i++) {
36     for (int j = 0; j < 4; j++) {
37       if (i == j)
38         continue;
39       if (parallelp(lines[i], lines[j]) && !samep(lines[i], lines[j]))
40         res++;
41     }
42   }
43 
44   return res;
45 }
46 
47 int vertical_count(vector<Line> &lines) {
48   int res = 0;
49 
50   for (int i = 0; i < 4; i++) {
51     for (int j = 0; j < 4; j++) {
52       if (i == j)
53         continue;
54       if (verticalp(lines[i], lines[j]))
55         res++;
56     }
57   }
58 
59   return res;
60 }
61 
62 bool rectanglep(vector<Line> &lines) {
63   int p_count = parallel_count(lines);
64   int v_count = vertical_count(lines);
65   return p_count == 4 && v_count == 8;
66 }
67 
68 int main() {
69   int n;
70   double x1, y1, x2, y2;
71 
72   cin >> n;
73   while (n--) {
74     vector<Line> lines;
75     for (int i = 0; i < 4; i++) {
76       cin >> x1 >> y1 >> x2 >> y2;
77       lines.push_back(Line(x1, y1, x2, y2));
78     }
79 
80     if (rectanglep(lines))
81       cout << "YES" << endl;
82     else
83       cout << "NO" << endl;
84   }
85   return 0;
86 }