hyz's blog
0%

CF 975E: Hag's Khashba

发表于

题意

有一个凸多边形，在两个钉子（位置在凸多边形的两个顶点上）的作用下，固定在了墙上。现在有两种操作，第一种操作是将其中一个钉子移走，等待凸多边形稳定后，再将钉子钉在某个位置上。第二种操作是询问某个点的坐标。

分析

这道题是典型的计算几何题，涉及到的知识大概有：

  1. 多边形重心的计算。
  2. 多边形的旋转。

多边形重心的公式可以在网上搜到，这里就不再赘述了（其实是因为贴不了数学公式）。

我们知道，假如多边形没有产生形变，那么它的重心与所有顶点的距离是不变的。因此，假如我们知道一个多边形的重心坐标以及重心与所有顶点的距离，再加上重心与所有顶点的角度差，我们就可以确定所有顶点的坐标了。需要注意的是，重心与其他所有顶点的角度差在重心变更时会产生变化，因此，我们需要进行角度变换。总的时间复杂度是O(n + q)。

下面的代码里有些形如cosl这样形式的三角函数，与cos这种普通三角函数的不同是：cosl的参数要求为long double，返回值也为long double，从而保证了精度。这道题不用cosl也能过，但用了更保险。

代码

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

#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

typedef pair<long double, long double> point;
point a[N], c;
long double ang[N], angle, dist[N], bx, by;
int n, q, t1, t2;

point getC() {
    long double area = 0, cx = 0, cy = 0;
    for(int i = 0; i < n; i++) {
        long double temp = a[i].x * a[(i+1)%n].y - a[i].y * a[(i+1)%n].x;
        area += temp;
        cx += (a[i].x + a[(i+1)%n].x) * temp;
        cy += (a[i].y + a[(i+1)%n].y) * temp;
    }
    area /= 2;
    cx /= 6 * area;
    cy /= 6 * area;
    return point(cx, cy);
}

point getPoint(int idx) {
    return point(c.x + dist[idx] * cosl(angle + ang[idx]), c.y + dist[idx] * sinl(angle + ang[idx]));
}

long double getDist(point a, point b) {
    return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    scanf("%d%d", &n, &q);
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &t1, &t2);
        a[i].x = t1;
        a[i].y = t2;
    }
    bx = a[0].x, by = a[0].y;
    for(int i = 0; i < n; i++) {
        a[i].x -= bx;
        a[i].y -= by;
    }
    c = getC();
    for(int i = 0; i < n; i++) {
        dist[i] = getDist(a[i], c);
        ang[i] = atan2l(a[i].y - c.y, a[i].x - c.x);
        if(ang[i] < 0)
            ang[i] += 2 * PI;
    }
    angle = 0;
    int i = 0, j = 1, op, x, y;
    point top, nxt;
    while(q--) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d%d", &x, &y);
            x--, y--;
            if(x == i) {
                i = y;
                top = getPoint(j);
                nxt = point(top.x, top.y - dist[j]);
            }
            else {
                j = y;
                top = getPoint(i);
                nxt = point(top.x, top.y - dist[i]);
            }
            angle += -PI/2 - atan2l(c.y - top.y, c.x - top.x);
            while(angle < 0)
                angle += 2 * PI;
            while(angle >= 2 * PI)
                angle -= 2 * PI;
            c = nxt;
        }
        else {
            scanf("%d", &x);
            point ans = getPoint(x-1);
            printf("%.10f %.10f\n", (double)(ans.x + bx), (double)(ans.y + by));
        }
    }

    return 0;
}