Sequence of points

发表于 更新于 分类于 ，

    给出n个二维平面上的点$a_0, a_1, a_2, \cdots, a_3$，现在有一个点$m_0$，

    每个$m_i$是$m_{i-1}$关于$a_{i-1 \bmod n}$的对称点。

    注意n为奇数。

    求解$m_j, j<1e^{18}$

Sequence of points

Created by LXC on Sat May 20 19:50:44 2023

https://codeforces.com/problemset/problem/24/C

ranting: 1800

tag: geometry, implementation, math

题意

给出n个二维平面上的点$a_0, a_1, a_2, \cdots, a_3$，现在有一个点$m_0$，
每个$m_i$是$m_{i-1}$关于$a_{i-1 \bmod n}$的对称点。

注意n为奇数。

求解$m_j, j<1e^{18}$

题解

$mx_i=2*mx-mx_{i-1}$

$my_i=2*my-my_{i-1}$

由于n为奇数，我们发现$mx_{2n} = mx_{0}, my_{2n} = my_{0}$

所以先求出前2n项m。然后$m_{j\bmod 2n}$为答案。

代码

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

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 200005
#define MOD 998244353
using namespace std;

int mx[N], my[N], ax[N], ay[N];

void sol() {
    ll n, j;
    cin >> n >> j;
    cin >> mx[0] >> my[0];
    for (int i = 0; i < n; i++) {
        cin >> ax[i] >> ay[i];
    }
    for (int i = 1; i < 2 * n; i++) {
        mx[i] = 2 * ax[(i - 1) % n] - mx[i - 1];
        my[i] = 2 * ay[(i - 1) % n] - my[i - 1];
    }
    cout << mx[j % (2 * n)] << " " << my[j % (2 * n)] << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}