题目类型 几何
题目意思
输入一个点 M0 和 n 个点 N0, N1, ... N(n-1) (1 <= n <= 1e5,, 且 n 是一个奇数)
其中 M1 和 M0 关于 N0 对称, M2 和 M1 关于 N1 对称 即 Mj 和 M(j-1) 关于 N(j-1) 对称
问 Mx 是多少 (1 <= x <= 1e18)
解题方法
模拟一下会发现 当进行 2 * n 次后 Mx 会回到 M0的位置 即只要模拟 x % (2*n) 次就可以得出结果
注意
输入的次数要用 long long 保存
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <map> #include <algorithm> #include <vector> #include <string> using namespace std; typedef long long LL; const int MAXN = 1e5 + 10; struct Node { int x, y; }a[MAXN]; int main() { LL n, m; while(cin>>n>>m) { Node b, tmp; scanf("%d%d", &b.x, &b.y); for( int i=0; i<n; i++ ) { scanf("%d%d", &a[i].x, &a[i].y); } m %= (2*n); for( int i=1; i<=m; i++ ) { //m1 a[0] m2 tmp.x = a[(i-1)%n].x * 2 - b.x; tmp.y = a[(i-1)%n].y * 2 - b.y; b.x = tmp.x; b.y = tmp.y; //printf("i = %d %d %d\n", i, b.x, b.y); } printf("%d %d\n", b.x, b.y); } return 0; }