当前位置: 代码迷 >> 综合 >> 【凸包】【KMP】Codeforces1017E The Supersonic Rocket
  详细解决方案

【凸包】【KMP】Codeforces1017E The Supersonic Rocket

热度:122   发布时间:2023-09-27 06:51:29.0

分析:

。。。第一次见CF服务器炸了,还好最后unrated了,不然这次死惨。。。

很容易想到,这两个多边形的凸包能通过旋转、平移最终重合,就必然满足条件。

所以就是判断两多边形是否全等。

额。。题解就是标题:顺时针地把两个凸包每个边的长度、每个点的旋转角储存下来(长度不开根号,旋转角用差积表示,这样都是整数)。

如果这两个序列能完全匹配,则说明能够重合。方法就是把其中一个串复制一遍粘在后面,然后在另一个序列上建KMP,然后依次匹配,看能否匹配到末尾。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<map>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 400010
#define EPS 1e-7
using namespace std;
typedef long long ll;
const double Pi=acos(-1);
struct node{ll x,y;node(){}node(ll xx,ll yy):x(xx),y(yy) {}node operator + (const node &a) const {return node(x+a.x,y+a.y);}node operator - (const node &a) const {return node(x-a.x,y-a.y);}node operator * (const double &t) const {return node(x*t,y*t);}double operator *(const node &a) const{return x*a.x+y*a.y;}double operator ^(const node &a) const{return x*a.y-y*a.x;}bool operator <(const node &a) const {return a.x!=x?x<a.x:y<a.y;}
};
bool cmp(node a,node b){return b<a;
}
class Curex{public:node p[MAXN],l1[MAXN];stack<node> s1,s;ll ans[MAXN];int n,cnt1,cnt2;void solve(node a1[],int &cnt){s.push(p[1]);s1.push(p[1]);s1.push(p[2]);for(int i=3;i<=n;i++){while(!s.empty()&&((p[i]-s.top())^(s1.top()-s.top()))<=0){s.pop();s1.pop();}s.push(s1.top());s1.push(p[i]);}while(!s1.empty()){a1[++cnt]=s1.top();s1.pop();}while(!s.empty())s.pop();}void init(int n1){n=n1;for(int i=1;i<=n;i++)SF("%I64d%I64d",&p[i].x,&p[i].y);sort(p+1,p+1+n);solve(l1,cnt1);sort(p+1,p+1+n,cmp);cnt1--;solve(l1,cnt1);cnt1--;cnt2=0;for(int i=1;i<=cnt1;i++){int las,nxt;if(i==1)las=cnt1;elselas=i-1;if(i==cnt1)nxt=1;elsenxt=i+1;ans[++cnt2]=(ll)((l1[nxt]-l1[i])*(l1[las]-l1[i]));ll xx=(l1[nxt]-l1[i]).x;ll yy=(l1[nxt]-l1[i]).y;ans[++cnt2]=xx*xx+yy*yy;}   }
}fir,sec;
int las[MAXN];
void build(ll a[]){int len=fir.cnt2;for(int i=0;i<len;i++){int x=i;while(x){x=las[x];if(a[x+1]==a[i+1]){las[i+1]=x+1;break;}}}
}
bool check(int n,ll a[],int m,ll b[]){int lasx=0;for(int i=1;i<=m;i++){while(lasx&&a[lasx+1]!=b[i])lasx=las[lasx];if(a[lasx+1]==b[i])lasx++;if(lasx==n)return 1;}return 0;
}
int main(){int n,m;SF("%d%d",&n,&m);fir.init(n);sec.init(m);if(fir.cnt1!=sec.cnt1){PF("NO");return 0;}build(fir.ans);for(int i=1;i<=sec.cnt2;i++)sec.ans[sec.cnt2+i]=sec.ans[i];sec.cnt2*=2;if(check(fir.cnt2,fir.ans,sec.cnt2,sec.ans))PF("YES\n");elsePF("NO\n");
}