[Codeforces975E] Hag's Khashba

做法

先求重心:随便找个点,把多边形划分成若干个三角形,求出每个三角形重心,按有向面积加权平均。

对于一个点 \((x_p,y_p)\),设 \(p = \begin{bmatrix} x_p \\ y_p \\ 1 \end{bmatrix}\)。把它绕 \((x_0,y_0)\) 逆时针旋转 \(c\) 弧度,相当于把 \(p\) 左乘一个矩阵 \(\begin{bmatrix} \cos c & -\sin c & x_0+\sin c y_0 - \cos c x_0 \\ \sin c & \cos c & y_0 - \cos c y_0-\sin c x_0 \\ 0 & 0 & 1 \end{bmatrix}\)。只需要记一个 \(3 \times 3\) 矩阵就能快速获得每个点的位置。旋转时考虑一下固定的点和重心的位置即可。

听(题解上)说需要把一个点移到 \((0,0)\) 避免精度误差。不知道不这样能不能过。

(样例 2 真的会转吗?)

时间复杂度 \(\mathcal O(n+m)\)

代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

const int maxn = 10010;
const ld eps = 1e-9;

int n, q, p1, p2;

struct Point {
ld x, y;
Point (ld x_=0, ld y_=0) : x(x_), y(y_) {}
ld abs() {
return sqrt(x * x + y * y);
}
} p[maxn], c;

Point operator*(const ld &k, const Point &p) {
return Point(k * p.x, k * p.y);
}

Point operator+(const Point &a, const Point &b) {
return Point(a.x + b.x, a.y + b.y);
}

Point operator-(const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}

ld operator*(const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
}

struct Matrix {
ld a[3][3];
} cur;

Matrix operator*(const Matrix &m1, const Matrix &m2) {
Matrix ret;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
ret.a[i][j] = 0;
for (int k = 0; k < 3; k++) {
ret.a[i][j] += m1.a[i][k] * m2.a[k][j];
}
}
}
return ret;
}

Point cal(Point s) {
return Point(cur.a[0][0] * s.x + cur.a[0][1] * s.y + cur.a[0][2], cur.a[1][0] * s.x + cur.a[1][1] * s.y + cur.a[1][2]);
}

int main() {
scanf("%d%d", &n, &q);
cur.a[0][0] = cur.a[1][1] = cur.a[2][2] = 1;
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d%d", &x, &y);
p[i].x = x, p[i].y = y;
}
Point _ = p[1];
for (int i = 1; i <= n; i++) p[i] = p[i] - _;
p1 = 1, p2 = 2;
ld S = 0; p[n+1] = p[1];
for (int i = 1; i <= n; i++) S += p[i] * p[i+1];
for (int i = 1; i <= n; i++) {
Point cc((p[i].x + p[i+1].x) / 3, (p[i].y + p[i+1].y) / 3);
c = c + p[i] * p[i+1] / S * cc;
}
for (int i = 1; i <= q; i++) {
int o; scanf("%d", &o);
if (o == 1) {
int f, t; scanf("%d%d", &f, &t);
if (f == p2) swap(p1, p2);
// 现在用 p2 旋转
Point nc = cal(c), np = cal(p[p2]);
Point d = nc - np;
/* if (d.x < eps && d.x > -eps) {
p1 = t;
continue;
} */
d = ld(1) / d.abs() * d;
ld co = - d.y, si = - d.x;
Matrix m;
m.a[0][0] = co, m.a[0][1] = -si, m.a[0][2] = np.x + si * np.y - co * np.x;
m.a[1][0] = si, m.a[1][1] = co, m.a[1][2] = np.y - co * np.y - si * np.x;
m.a[2][0] = 0, m.a[2][1] = 0, m.a[2][2] = 1;
cur = m * cur;
p1 = t;
} else {
int v; scanf("%d", &v);
Point res = cal(p[v]);
printf("%.10lf %.10lf\n", double (res.x + _.x), double (res.y + _.y));
}
}
return 0;
}