原题传送门：Codeforces 1017E
洛谷博客传送门：洛咕
题目大意就是让你求两个凸包，然后验证它们是否旋转同构
旋转同构其实类似字符串的循环同构
所以将凸包变成线段-夹角-线段-夹角……的数列形式
其中一个倍长，另一个kmp匹配即可
注意，这时候凸包的边上不能有点！
#include <bits/stdc++.h>
#define eps 1e-8
#define delta 0.98
#define Get(a, b) atan2(a, b)
using namespace std;const int MAXN = 100100;struct Point {double x, y;Point () {}Point (double _x, double _y) : x(_x), y(_y) {}
};typedef Point Vector;
typedef Point Polygon[MAXN];template <typename T> inline void read(T &x) {int c = getchar();bool f = false;for (x = 0; !isdigit(c); c = getchar()) {if (c == '-') {f = true;}}for (; isdigit(c); c = getchar()) {x = x * 10 + c - '0';}if (f) {x = -x;}
}Vector read_Vector() {double x, y;scanf("%lf%lf", &x, &y);return Vector(x, y);
} int dcmp(double x) {if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;}Vector operator + (Vector A, Vector B) {return Vector(A.x + B.x, A.y + B.y);}Vector operator - (Vector A, Vector B) {return Vector(A.x - B.x, A.y - B.y);}Vector operator * (Vector A, double B) {return Vector(A.x * B, A.y * B);}Vector operator / (Vector A, double B) {return Vector(A.x / B, A.y / B);}bool operator == (const Vector&a, const Vector&b) {return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;}double Dot(Vector A, Vector B) {return A.x * B.x + A.y * B.y;}double Length(Vector A) {return sqrt(A.x * A. x + A. y * A.y);}double Angle(Vector A, Vector B) {return acos(Dot(A, B) / Length(A) / Length(B));}double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}double GetS(Vector A, Vector B, Vector C) {return Cross(B - A, C - A);}bool operator < (Point a, Point b) {return a.x < b.x || (a.x == b.x && a.y < b.y);
}int ConvexHull(Point * p, int N, Point * ch) {sort(p, p + N);int sum = 0;for(int i = 0; i < N; i++) {while(sum > 1 && dcmp(Cross(ch[sum - 1] - ch[sum - 2], p[i] - ch[sum - 2]) >= 0)) sum--;ch[sum++] = p[i];}int k = sum;for(int i = N - 2; i >= 0; i--) {while(sum > k && dcmp(Cross(ch[sum - 1] - ch[sum - 2], p[i] - ch[sum - 2])) >= 0) sum--;ch[sum++] = p[i];}if(N > 1) sum--;return sum;
}bool chdb (double a, double b) {return fabs(a - b) <= eps;
}int nxt[MAXN << 1];bool KmpSearch(double * s, double * p, int sLen, int pLen) { int i = 0; int j = 0; while(i < sLen && j < pLen) { if(!chdb(s[i], p[j])) {if(j == 0) i++; j = nxt[j];} while(j < pLen && chdb(s[i], p[j])) i++, j++;if (j == pLen) return 1;} return 0;
} void GetNext(double * p, int Nxt[], int pLen) { Nxt[0] = -1;Nxt[1] = 0; int j = 0, i = 1;for(i = 1; i < pLen; i++) { while(j > 0 && !chdb(p[i], p[j])) j = Nxt[j]; if(chdb(p[i], p[j])) j++; Nxt[i + 1] = j;}
} int n, m;
Polygon p1, p2, c1, c2;
int sum1, sum2, cnts, cntt;
double S[MAXN << 2], T[MAXN << 1];void print(double * s, int len) {for(int i = 0; i < len; i++) {printf("%.2lf%c", s[i], i == len - 1 ? '\n' : ' ');}
}signed main() {read(n), read(m);for(int i = 0; i < n; i++) p1[i] = read_Vector();for(int i = 0; i < m; i++) p2[i] = read_Vector();sum1 = ConvexHull(p1, n, c1);sum2 = ConvexHull(p2, m, c2);if(sum1 != sum2) {puts("NO");return 0;}c1[sum1] = c1[0]; c1[sum1 + 1] = c1[1];c2[sum2] = c2[0]; c2[sum2 + 1] = c2[1];for(int i = 0; i < sum1; i++) {S[cnts++] = Length(c1[i + 1] - c1[i]);S[cnts++] = Angle(c1[i + 2] - c1[i + 1], c1[i + 1] - c1[i]);}for(int i = 0; i < sum2; i++) {T[cntt++] = Length(c2[i + 1] - c2[i]);T[cntt++] = Angle(c2[i + 2] - c2[i + 1], c2[i + 1] - c2[i]);}for(int i = cnts; i < cnts * 2 - 1; i++) S[i] = S[i - cnts];GetNext(T, nxt, cntt);if(KmpSearch(S, T, cnts * 2 - 2, cntt - 1)) puts("YES");else puts("NO");return 0;
}