题目概述

判断两个凸包是否同构，即是否能平移+旋转使得两个凸包重合。

解题报告

原题意是说两个点之间都会建新点，建完之后新点之间也会建新点，那么其实很明显所有点构成了一个凸包围成的凸多边形……打比赛的时候我竟然一脸懵逼……

凸包同构是个啥？其实只需要交错记录下所有角(点积)和边(距离)，做KMP就行了。

但是由于起始位置的问题我们需要把其中一个串复制一份。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
const int maxn=100000,maxt=maxn<<2;
typedef long long LL;typedef pair<int,int> vec;

int n,m;vec A[maxn+5],B[maxn+5];
int fai[maxt+5];LL a[maxt+5],b[maxt+5];

inline vec operator - (const vec &a,const vec &b) {return mp(a.fr-b.fr,a.sc-b.sc);}
inline LL Dot(const vec &a,const vec &b) {return (LL)a.fr*b.fr+(LL)a.sc*b.sc;}
inline LL Cross(const vec &a,const vec &b) {return (LL)a.fr*b.sc-(LL)a.sc*b.fr;}
inline LL sqrdis(const vec &a,const vec &b) {return (LL)(a.fr-b.fr)*(a.fr-b.fr)+(LL)(a.sc-b.sc)*(a.sc-b.sc);}
#define L(x) ((x)-1<1?top:(x)-1)
#define R(x) ((x)+1>top?1:(x)+1)
inline int Andrew(vec *a,int n,LL *s){
    static int top;static vec stk[maxn+5];top=0;sort(a+1,a+1+n);
    for (int i=1;i<=n;stk[++top]=a[i++]) while (top>1&&Cross(stk[top]-stk[top-1],a[i]-stk[top-1])<=0) top--;
    for (int i=n,t=top;i;stk[++top]=a[i--]) while (top>t&&Cross(stk[top]-stk[top-1],a[i]-stk[top-1])<=0) top--;
    for (int i=(n=0,top--,1);i<=top;i++) s[++n]=Dot(stk[i]-stk[L(i)],stk[R(i)]-stk[L(i)]),s[++n]=sqrdis(stk[i],stk[R(i)]);return n;
}
inline void getfai(LL *b){
    for (int i=2,j=0;i<=m;i++){
        while (j&&b[i]!=b[j+1]) j=fai[j];
        j+=b[i]==b[j+1];fai[i]=j;
    }
}
inline bool Find(LL *a){
    for (int i=1,j=0;i<=(n<<1);i++){
        while (j&&a[i]!=b[j+1]) j=fai[j];
        j+=a[i]==b[j+1];if (j==m) return true;
    }return false;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d%d",&A[i].fr,&A[i].sc);n=Andrew(A,n,a);
    for (int i=1;i<=m;i++) scanf("%d%d",&B[i].fr,&B[i].sc);m=Andrew(B,m,b);
    if (n!=m) return puts("NO"),0;for (int i=1;i<=n;i++) a[n+i]=a[i];
    getfai(b);return Find(a)?puts("YES"):puts("NO"),0;
}