[ZJOI2008]无序运动Movement

Description

D博士对物理有着深入的研究，经典物理、天体物理、量子物理都有着以他的名字命名的定理。最近D博士着迷于研究粒子运动的无规则性。对圣经深信不疑的他相信，上帝创造的任何事物必然是有序的、有理可循的，而不是无规则的、混沌的。经过长时间的研究，D博士找到了很多出现相当频繁的轨迹片断，他把这些轨迹片断储存在一个很大的数据库内。他需要你帮助他写一个程序，对于一个给出的粒子运动轨迹，统计数据库中每个轨迹片断的出现的次数。为清楚起见，我们定义一个粒子的轨迹为二维平面上的一个点列（P1, P2, … PN）。点列P的一个子列[i, j]定义为P中一段连续的子序列（Pi, Pi+1, … Pj）。点列P的一个子列[u, v]被称为点列Q = (Q1, Q2 … Qv-u+1)在P中的一次出现，当且仅当Q经过有限次的平移、旋转、翻转、放缩之后得到Q’满足Q’k = Pu+k-1（k =1 … u – v + 1）。对平面X-Y进行四种操作的解释平移设平移向量为(dx, dy)，则任意点(x,y)平移后的结果为(x+dx, y+dy) 旋转设旋转角为t，则任意点(x,y)旋转后的结果为 (x cos t – y sin t, x sin t + y cos t)翻转任意点(x,y) 翻转后的结果为(x, -y) 放缩设放缩比例为p (p ≠ 0)，则任意点(x,y)放缩后的结果为(px,py)

Input

第一行两个整数N、M，分别描述待处理的粒子运动轨迹的点列大小与数据库内的轨迹片断个数。接下来M行依次给出每个轨迹片断。每行先是一个正整数K，表示该轨迹片断点列的长度。然后2K个整数，依次描述点列中的K个点的横坐标与纵坐标。接下来一行2N个整数，依次描述待处理的粒子运动轨迹的点列中N个点的横坐标与纵坐标。

注：输入中的每条轨迹中任意相邻两点不会相同。

Output

应包含M行，依次给出每个片段在待处理运动轨迹中的出现次数。

Sample Input

3 2

2 17 0 10 1

3 0 0 1 0 1 -1

0 0 1 0 1 1

Sample Output

2

1

HINT

N, K ≤ 200 000，片段总长度 ≤ 1600000，输入中给出所有点坐标绝对值均不大于10 000。

考虑能够匹配，两个图形肯定是相似的

所以我们可以直接记录相邻两个边的长度比和夹角

然后炸精度……

换个方式记录，边长可以改为记录相邻两边的边长长度平方最简比（因为都是整点，平方后肯定是整数）

然后角度怎么记？可以用带符号的两边叉积点积最简比记录

翻转的话，把匹配串翻转一下再匹配就好了

注意判断翻转之后是否依然相似

然后AC自动机大力跑，Map存边即可，由于字符集很大，暴力跳Fail即可

/*program from Wolfycz*/

#include<map>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define Fi first

#define Se second

#define MK make_pair

#define inf 0x7f7f7f7f

#define sqr(x) ((x)*(x))

#define For(T,i,x) for (T::iterator i=x.begin();i!=x.end();i++)

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef pair<int,int> pii;

typedef unsigned long long ull;

inline char gc(){

	static char buf[1000000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;

}

inline int frd(){

	int x=0,f=1; char ch=gc();

	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline int read(){

	int x=0,f=1; char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x<0)	putchar('-'),x=-x;

	if (x>9)	print(x/10);

	putchar(x%10+'0');

}

const int N=2e5;

int Ans[N+10];

struct complex{

	int x,y;

	complex(int _x=0,int _y=0){x=_x,y=_y;}

	int operator *(const complex &tis)const{return x*tis.y-y*tis.x;}

	int operator /(const complex &tis)const{return x*tis.x+y*tis.y;}

	complex operator +(const complex &tis)const{return complex(x+tis.x,y+tis.y);}

	complex operator -(const complex &tis)const{return complex(x-tis.x,y-tis.y);}

	void insert(int _x,int _y){x=_x,y=_y;}

};

struct node{

	pii scl,rte;//scaling,rotate

	int gcd(int a,int b){return !b?a:gcd(b,a%b);}

	pii work(pii tmp){

		int d=max(1,gcd(abs(tmp.Fi),abs(tmp.Se)));

		tmp.Fi/=d,tmp.Se/=d;

		return tmp;

	}

	node(pii _scl=MK(0,0),pii _rte=MK(0,0)){scl=work(_scl),rte=work(_rte);}

	void insert(pii _scl,pii _rte){scl=work(_scl),rte=work(_rte);}

	bool operator <(const node &tis)const{return scl!=tis.scl?scl<tis.scl:rte<tis.rte;}

	bool operator ==(const node &tis)const{return scl==tis.scl&&rte==tis.rte;}

	bool operator !=(const node &tis)const{return !(*this==tis);}

};

struct S1{

	map<node,int>trie[N+10];

	int fail[N+10],cnt[N+10],tot,root;

	vector<int>End[N+10];

	S1(){tot=root=1;}

	void insert(node *s,int n,int ID){

		int p=root;

		for (int i=1;i<=n;i++){

			map<node,int>::iterator I=trie[p].find(s[i]);

			if (I==trie[p].end())	I=trie[p].insert(map<node,int>::value_type(s[i],++tot)).Fi;

			p=I->Se;

		}

		End[p].push_back(ID);

	}

	void make_fail(){

		static int h[N+10];

		int head=1,tail=1; h[1]=root;

		for (;head<=tail;head++){

			int Now=h[head];

			for (map<node,int>::iterator it=trie[Now].begin();it!=trie[Now].end();it++){

				int p=fail[Now];

				while (p&&trie[p].find(it->Fi)==trie[p].end())	p=fail[p];

				fail[it->Se]=p?trie[p].find(it->Fi)->Se:root;

				h[++tail]=it->Se;

			}

		}

	}

	void work(node *s,int len){

		int p=root;

		for (int i=1;i<=len;i++){

			while (p&&trie[p].find(s[i])==trie[p].end())	p=fail[p];

			p=p?trie[p].find(s[i])->Se:root;

			for (int x=p;x;x=fail[x])	cnt[x]++;

		}

	}

	void updata(){

		for (int i=1;i<=tot;i++)

			For(vector<int>,I,End[i])

				Ans[*I]+=cnt[i];

	}

}AC;//Aho-Corasick automaton

int dis(pii x,pii y){return sqr(x.Fi-y.Fi)+sqr(x.Se-y.Se);}

int A[2][N+10],Len[N+10];

void init(node *R,int &len,int n){

	len=0;

	for (int i=2;i<n;i++){

		pii Dis=MK(dis(MK(A[0][i+1],A[1][i+1]),MK(A[0][i],A[1][i])),dis(MK(A[0][i],A[1][i]),MK(A[0][i-1],A[1][i-1])));

		complex x(A[0][i-1]-A[0][i],A[1][i-1]-A[1][i]),y(A[0][i+1]-A[0][i],A[1][i+1]-A[1][i]);

		R[++len].insert(Dis,MK(x*y,x/y));

	}

}

bool Dif[N+10];

node R[N+10],tmp[N+10];

int main(){

	int n=read(),m=read(),len;

	for (int i=1;i<=m;i++){

		Len[i]=read();

		for (int j=1;j<=Len[i];j++)	A[0][j]=read(),A[1][j]=read();

		if (Len[i]<3)	continue;

		init(R,len,Len[i]);

		AC.insert(R,len,i);

		for (int j=1;j<=Len[i];j++)	A[1][j]=-A[1][j];

		init(tmp,len,Len[i]);

		for (int j=1;j<=len;j++)	Dif[i]|=(R[j]!=tmp[j]);

		Dif[i]^=1;

	}

	AC.make_fail();

	for (int i=1;i<=n;i++)	A[0][i]=read(),A[1][i]=read();

	if (n>2){

		init(R,len,n),AC.work(R,len);

		for (int i=1;i<=n;i++)	A[1][i]=-A[1][i];

		init(R,len,n),AC.work(R,len);

	}

	AC.updata();

	for (int i=1;i<=m;i++)	printf("%d\n",Len[i]==1?n:Len[i]==2?n-1:Ans[i]>>Dif[i]);

	return 0;

}

巴特西

[ZJOI2008]无序运动Movement

最新文章

热门文章