题解 CF1017E 【The Supersonic Rocket】
KKarshilov
2018-08-10 18:28:38
中规中矩的做法，题目要求的是给出两个点集，求出它们的凸包并判断是否旋转同构
举个例子：
(0, 0) (1, 0) (0, 1)
(1, 0) (1, 1) (0, 1)
这就是一组旋转同构
并没有参加比赛，但是hyc在群里提了这道题，让我们思考
求解凸包直接使用基于水平序的Andrew算法，具体做法请参考[凸包模板](https://www.luogu.org/problemnew/show/P2742)
我一看，旋转同构？如果能找到对应点，拆开成一条链多好判啊
当然，我并不知道怎么找对应点，如果有巨佬会请告诉我
然后我就从这个思路想到了某个很像的东西
最小循环同构！或者说最小表示法
但是和这题还是没什么关系，不过由这个点我们就可以想到很多东西：旋转同构转循环同构
字符串的循环同构本身就是将字符串首位相接成环，从不同的地方断开就是不同的字符串，如此得到的的字符串都是循环同构的
那么怎样将这个东西用在凸包上，或者多边形上呢？
我们要保证凸包的信息不变且可以识别，并且和字符串具有某些共性以便于以后的操作
凸包的信息集中在点上，对于每个点，它同时属于两条边和一个角
所以将凸包拆分成边-角-边-角-边……的形式，边用长度表示，角用弧度表示，就是一个数列了，比如:(1, 0) (0, 1) (0, 0)
数列形式: 1.41421--Pi/4--1--Pi/2--1--Pi/4
然后我们的问题就变成了判断两个数列循环同构
将其中一个复制一倍接在尾部，用另一个数列去匹配，采用KMP算法即可解决
```cpp
#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;
}
```