鸡算几何
原题链接
TAG：计算几何
思路
只有操作 3 能达到的效果就是将 L 形铁丝沿着一边进行 180° 的翻转，可以利用叉乘的正负性进行判断是否进行了翻转。
当一个向量在另一个向量 逆时针 旋转180°的范围内，叉积为正；当一个向量在另一个向量 顺时针 旋转180°的范围内，叉积为负。
因此可以先通过叉积来匹配铁丝 ABC 和 DEF，后面根据 AB 边和 DE 边的长短是否相等来判断是否可能进行了操作 3。计算长度可以用点积。
代码
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
66
67
68
69
70
71
72 | #include <bits/stdc++.h>
using namespace std;
using T = double;
struct Point {
T x;
T y;
Point(T x = 0, T y = 0) : x(x), y(y) {}
Point &operator+=(const Point &p) {
x += p.x, y += p.y;
return *this;
}
Point &operator-=(const Point &p) {
x -= p.x, y -= p.y;
return *this;
}
Point &operator*=(const T &v) {
x *= v, y *= v;
return *this;
}
friend Point operator-(const Point &p) {
return Point(-p.x, -p.y);
}
friend Point operator+(Point lhs, const Point &rhs) {
return lhs += rhs;
}
friend Point operator-(Point lhs, const Point &rhs) {
return lhs -= rhs;
}
friend Point operator*(Point lhs, const T &rhs) {
return lhs *= rhs;
}
};
T dot(const Point &a, const Point &b) {
return a.x * b.x + a.y * b.y;
}
T cross(const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
}
void solve() {
Point p[6];
for (int i = 0; i < 6; i++) {
cin >> p[i].x >> p[i].y;
}
if (cross(p[1] - p[0], p[1] - p[2]) < 0) swap(p[0], p[2]);
if (cross(p[4] - p[3], p[4] - p[5]) < 0) swap(p[3], p[5]);
double len0 = dot(p[0] - p[1], p[0] - p[1]);
double len1 = dot(p[3] - p[4], p[3] - p[4]);
if (abs(len0 - len1) > 1e-6) cout << "YES\n";
else cout << "NO\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|