Codeforces Round 502 E. The Supersonic Rocket 凸包、kmp

题目链接

题目大意

平面上给定两个点集，判定两个点集分别形成的凸多边形能否通过旋转、平移重合。

点集大小 $\le$ $10^5$，坐标范围 [0, $10^8$ ].

思路

题意很明显，先求出凸包再判断两凸包是否同构。这里用的 $Andrew$ 算法求。判同构的话，将俩凸包都转化成字符串的形式，用 $kmp$ 去匹配从而判断该串中是否存在另外一个凸包所对应的字符串。

code

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>using namespace std;
const int N = 1e5 + 100, M = 2e5 + 100;
int n, m, id;
int tmp1, tmp2, minx, ans;
pair<int, int> s[M];
pair<int, int> t[M];
int nxt[M];struct Point
{int x, y;
} tmp, st;
Point a[N];
vector<Point> v;
vector<Point> e[3];int dop(Point a, Point b)
{return a.x * b.x + a.y * b.y;
}
int crp(Point a, Point b)
{return a.x * b.y - a.y * b.x;
}
int len(Point a, Point b)
{return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
Point mins(Point a, Point b)
{Point c;c.x = b.x - a.x;c.y = b.y - a.y;return c;
}
bool cmp1(Point a, Point b)
{if (a.x == b.x){return a.y < b.y;}return a.x < b.x;
}
bool cmp(Point a, Point b)
{int sum1 = crp(mins(st, a), mins(st, b));if (sum1 == 0.0){if (a.x == b.x){return a.y < b.y;}return a.x < a.x;}return sum1 > 0.0;
}
void get_nxt()
{int i = 0, j = -1;nxt[0] = -1;while (i < 2 * e[1].size()){if (j == -1 || s[i] == s[j]){i++;j++;nxt[i] = j;}else{j = nxt[j];}}
}
bool kmp()
{int i = 0, j = 0;while (i < 2 * e[1].size()){if (j == -1 || s[i] == t[j]){i++;j++;}else if (j == e[2].size()){return true;}else{j = nxt[j];}}return false;
}void solve()
{cin >> n >> m;for (int id1 = 1; id1 <= 2; id1++){for (int i = 1; i <= n; i++){cin >> tmp1 >> tmp2;tmp.x = tmp1, tmp.y = tmp2;a[i] = tmp;}minx = 0x3f3f3f3f;sort(a + 1, a + n + 1, cmp1);st.x = a[1].x, st.y = a[1].y;id = 1;for (int i = 2; i <= n; i++){v.push_back(a[i]);}sort(v.begin(), v.end(), cmp);e[id1].push_back(a[id]);for (auto x : v){if (e[id1].size() <= 1){e[id1].push_back(x);continue;}bool fl = false;while (e[id1].size() >= 2){int sum1 = crp(mins(e[id1][e[id1].size() - 1], e[id1][e[id1].size() - 2]), mins(e[id1][e[id1].size() - 1], x));if (sum1 >= 0.0){e[id1].pop_back();}else{e[id1].push_back(x);fl = true;break;}}if (!fl){e[id1].push_back(x);}}n = m;v.clear();}if (e[1].size() != e[2].size()){cout << "NO\n";return;}for (int i = 0; i < e[1].size(); i++){s[i] = {(e[1][i].x - e[1][(i + 1) % e[1].size()].x) * (e[1][i].x - e[1][(i + 1) % e[1].size()].x) + (e[1][i].y - e[1][(i + 1) % e[1].size()].y) * (e[1][i].y - e[1][(i + 1) % e[1].size()].y), dop(mins(e[1][(i + 1) % e[1].size()], e[1][i]), mins(e[1][(i + 1) % e[1].size()], e[1][(i + 2) % e[1].size()]))};}for (int i = 0; i < e[1].size(); i++){s[i + e[1].size()] = s[i];}for (int i = 0; i < e[2].size(); i++){t[i] = {(e[2][i].x - e[2][(i + 1) % e[2].size()].x) * (e[2][i].x - e[2][(i + 1) % e[2].size()].x) + (e[2][i].y - e[2][(i + 1) % e[2].size()].y) * (e[2][i].y - e[2][(i + 1) % e[2].size()].y), dop(mins(e[2][(i + 1) % e[2].size()], e[2][i]), mins(e[2][(i + 1) % e[2].size()], e[2][(i + 2) % e[2].size()]))};}get_nxt();cout << (kmp() ? "YES" : "NO");
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int tp = 1;// cin >> t;while (tp--)solve();return 0;
}