NC20475. [ZJOI2008]无序运动MOVEMENT
描述
输入描述
第一行两个整数N、M，分别描述待处理的粒子运动轨迹的点列大小与数据库内的轨迹片断个数。
接下来M行依次给出每个轨迹片断。每行先是一个正整数K，表示该轨迹片断点列的长度。
然后2K个整数，依次描述点列中的K个点的横坐标与纵坐标。
接下来一行2N个整数，依次描述待处理的粒子运动轨迹的点列中N个点的横坐标与纵坐标。
注：输入中的每条轨迹中任意相邻两点不会相同。
输出描述
应包含M行，依次给出每个片段在待处理运动轨迹中的出现次数。
示例1
输入:
3 2 2 17 0 10 1 3 0 0 1 0 1 -1 0 0 1 0 1 1
输出:
2 1
C++14(g++5.4) 解法, 执行用时: 355ms, 内存消耗: 18004K, 提交时间: 2020-04-02 13:48:10
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+9;
int n,m,k,tot=0,fail[maxn],last[maxn],cnt[maxn],ans[maxn],tp[maxn];
struct point{
int x,y;
point operator - (const point &b){return point{x-b.x,y-b.y};}
int operator * (const point &b) {return x*b.y-y*b.x;}
int operator ^ (const point &b) {return x*b.x+y*b.y;}
}po[maxn];
struct node{
int a,b,c,d;
bool operator < (const node &x) const{
if(a!=x.a) return a<x.a;
if(b!=x.b) return b<x.b;
if(c!=x.c) return c<x.c;
return d<x.d;
}
}s[maxn];
node change(point a,point b,point c)
{
node an;
an.a=(b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
an.b=(c.x-b.x)*(c.x-b.x)+(c.y-b.y)*(c.y-b.y);
an.c=(b-a)*(c-b);
an.d=(b-a)^(c-b);
int t=__gcd(an.a,an.b);
if(t!=0) an.a/=t,an.b/=t;
t=__gcd(abs(an.c),abs(an.d));
if(t!=0) an.c/=t,an.d/=t;
return an;
}
map<node,int> nex[maxn];
vector<int> ed[maxn];
#define iter map<node,int>::iterator
void ins(int len,int id)
{
int now=0;
for(int i=1;i<=len;i++)
{
iter it=nex[now].find(s[i]);
if(it==nex[now].end()) now=nex[now][s[i]]=++tot;
else now=it->second;
}
ed[now].push_back(id);
}
void build()
{
queue<int> que;
for(iter it=nex[0].begin();it!=nex[0].end();it++) que.push(it->second);
while(!que.empty())
{
int now=que.front();
que.pop();
for(iter it=nex[now].begin();it!=nex[now].end();it++)
{
node a=it->first;
int b=it->second,c=fail[now];
while(c&&nex[c].find(a)==nex[c].end()) c=fail[c];
if(nex[c].find(a)!=nex[c].end()) c=nex[c][a];
fail[b]=c;
last[b]=ed[c].empty()?last[c]:c;
que.push(b);
}
}
}
void solve()
{
int now=0;
for(int i=1;i<=n-2;i++)
{
int x=now;
while(x&&nex[x].find(s[i])==nex[x].end()) x=fail[x];
if(nex[x].find(s[i])!=nex[x].end())
x=nex[x][s[i]];
now=x;
for(;x;x=last[x]) cnt[x]++;
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int flag=1;
scanf("%d",&k);
for(int j=1;j<=k;j++) scanf("%d %d",&po[j].x,&po[j].y);
if(k<=2)
{ans[i]=n-1;continue;}
for(int j=2;j<k;j++)
{
s[j-1]=change(po[j-1],po[j],po[j+1]);
if(s[j-1].c) flag=0;
}
if(flag) tp[i]=1;
ins(k-2,i);
}
build();
for(int i=1;i<=n;i++) scanf("%d %d",&po[i].x,&po[i].y);
for(int i=2;i<n;i++) s[i-1]=change(po[i-1],po[i],po[i+1]);
solve();
for(int i=1;i<=n;i++) po[i].x=-po[i].x;
for(int i=2;i<n;i++) s[i-1]=change(po[i-1],po[i],po[i+1]);
solve();
for(int i=1;i<=tot;i++)
{
for(int j=0;j<ed[i].size();j++) ans[ed[i][j]]+=cnt[i];
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]/(tp[i]+1));
return 0;
}
C++ 解法, 执行用时: 106ms, 内存消耗: 87308K, 提交时间: 2021-05-21 16:54:03
#include<bits/stdc++.h>
const int N=1600007;
char buf[30000007],*ptr=buf-1;
int _(){
int x=0,f=1,c=*++ptr;
while(c<48)c=='-'&&(f=-1),c=*++ptr;
while(c>47)x=x*10+c-48,c=*++ptr;
return x*f;
}
int gcd(int a,int b){
for(int c;b;c=a,a=b,b=c%b);
return a;
}
int dis(int x,int y){
return x*x+y*y;
}
int n,m,x[N],y[N],e[N],ans[N];
bool re[N];
struct tri{
int a,b,c,d;
tri(int w){
int x1=x[w]-x[w-1],y1=y[w]-y[w-1],x2=x[w]-x[w+1],y2=y[w]-y[w+1];
a=dis(x1,y1);
b=dis(x2,y2);
c=dis(x1-x2,y1-y2);
int g=gcd(a,gcd(b,c));
if(g>1)a/=g,b/=g,c/=g;
d=x1*y2-x2*y1;
d=d<0?-1:d>0;
}
bool operator<(tri w)const{
return a!=w.a?a<w.a:b!=w.b?b<w.b:c!=w.c?c<w.c:d<w.d;
}
};
std::map<tri,int>nx[N];
int p=1,fa[N],deg[N],t[N],q[N],ql=0,qr=0;
int main(){
buf[fread(buf,1,sizeof(buf),stdin)]=0;
n=_();m=_();
for(int i=0;i<m;++i){
int c=_();
for(int j=0;j<c;++j){
x[j]=_();y[j]=_();
}
if(c<3)ans[i]=n+1-c,re[i]=1;
else{
int w=1;
for(int j=2;j<c;++j){
tri t(j-1);
if(t.d)re[i]=1;
if(nx[w].find(t)==nx[w].end())nx[w][t]=++p;
w=nx[w][t];
}
e[i]=w;
}
}
ql=qr=0;q[++qr]=1;
while(ql!=qr){
int w=q[++ql];
for(std::map<tri,int>::iterator it=nx[w].begin();it!=nx[w].end();++it){
int u=it->second,v=fa[w];
q[++qr]=u;
while(v&&nx[v].find(it->first)==nx[v].end())v=fa[v];
fa[u]=v?nx[v][it->first]:1;
}
}
for(int i=0;i<n;++i){
x[i]=_();y[i]=_();
}
int w=1;
for(int i=2;i<n;++i){
tri t(i-1);
while(w&&nx[w].find(t)==nx[w].end())w=fa[w];
w=w?nx[w][t]:1;
++::t[w];
}
for(int i=0;i<n;++i)y[i]=-y[i];
w=1;
for(int i=2;i<n;++i){
tri t(i-1);
while(w&&nx[w].find(t)==nx[w].end())w=fa[w];
w=w?nx[w][t]:1;
++::t[w];
}
ql=qr=0;
for(int i=1;i<=p;++i)++deg[fa[i]];
for(int i=1;i<=p;++i)if(!deg[i])q[++qr]=i;
deg[0]=0x3f3f3f3f;
while(ql!=qr){
int w=q[++ql],f=fa[w];
t[f]+=t[w];
if(!--deg[f])q[++qr]=f;
}
for(int i=0;i<m;++i)if(e[i])ans[i]=t[e[i]];
for(int i=0;i<m;++i)printf("%d\n",re[i]?ans[i]:ans[i]>>1);
return 0;
}