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 1Sample Output
2
1Solution
考慮如果能匹配上，那么兩個圖形必定相似。
所以一個很簡單的想法就是：記錄相鄰兩條邊的邊長之比和夾角。
但是這樣顯然由于精度過低，不可行。所以修改一下記錄的東西就變成了：
記錄兩邊的邊長平方的最簡比和帶符號的兩邊向量點積叉積最簡比，一共四個整數。
注意這里先不管翻轉操作，如果帶上翻轉操作的話，把匹配串翻一下再做一遍就好了。
然后建\(AC\)自動機，用\(map\)存邊，把串丟上去跑就行了。
由于這里字符集過大只能暴力跳\(fail\)指針。
看起來能過就行了（逃。
#include<bits/stdc++.h>
using namespace std;void read(int &x) {x=0;int f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}void print(int x) {if(x<0) putchar('-'),x=-x;if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}const int maxn = 2e5+10;#define sqr(x) ((x)*(x))int n,m,spj[maxn],tot,fail[maxn],cnt[maxn],lst[maxn],ans[maxn],tp[maxn];struct point {int x,y;point operator - (const point &rhs) const {return (point){x-rhs.x,y-rhs.y};}int operator * (const point &rhs) const {return x*rhs.y-y*rhs.x;}int operator ^ (const point &rhs) const {return x*rhs.x+y*rhs.y;}
}s[maxn];struct node {int a,b,c,d;bool operator < (const node &rhs) const {if(a!=rhs.a) return a<rhs.a;if(b!=rhs.b) return b<rhs.b;if(c!=rhs.c) return c<rhs.c;return d<rhs.d;}
}r[maxn];map<node,int > e[maxn];
vector <int > ed[maxn];#define iter map<node,int > :: iterator void ins(int w,int rs) {int now=0;for(int i=1;i<=w;i++) {iter it=e[now].find(r[i]);if(it==e[now].end()) now=(e[now][r[i]]=++tot);else now=it -> second;}ed[now].push_back(rs);
}void build() {queue<int > q;for(iter i=e[0].begin();i!=e[0].end();i++) q.push(i -> second);while(!q.empty()) {int now=q.front();q.pop();for(iter i=e[now].begin();i!=e[now].end();i++) {node a=i -> first;int b=i -> second,c=fail[now];for(;c&&e[c].find(a)==e[c].end();c=fail[c]);if(e[c].find(a)!=e[c].end()) c=e[c][a];fail[b]=c;lst[b]=ed[c].empty()?lst[c]:c;q.push(b);}}
}node trans(point A,point B,point C) {int a=sqr(B.x-A.x)+sqr(B.y-A.y);int b=sqr(C.x-B.x)+sqr(C.y-B.y);int c=(C-B)*(B-A),d=(C-B)^(B-A);int t=__gcd(a,b);a/=t,b/=t;t=__gcd(abs(c),abs(d)),c/=t,d/=t;return (node){a,b,c,d};
}void solve() {int now=0;for(int i=1;i<=n-2;i++) {int x=now;for(;x&&e[x].find(r[i])==e[x].end();x=fail[x]);if(e[x].find(r[i])!=e[x].end()) x=e[x][r[i]];now=x;for(;x;x=lst[x]) cnt[x]++;}
}int main() {read(n),read(m);for(int i=1;i<=m;i++) {int k,flag=1;read(k);for(int j=1;j<=k;j++) read(s[j].x),read(s[j].y);for(int j=2;j<k;j++) {r[j-1]=trans(s[j-1],s[j],s[j+1]);if(r[j-1].c) flag=0;}if(flag) spj[i]=1;if(k-2>0) ins(k-2,i),tp[i]=-1;else tp[i]=k;}build();for(int i=1;i<=n;i++) read(s[i].x),read(s[i].y);for(int i=2;i<n;i++) r[i-1]=trans(s[i-1],s[i],s[i+1]);solve();for(int i=1;i<=n;i++) s[i].x=-s[i].x;for(int i=2;i<n;i++) r[i-1]=trans(s[i-1],s[i],s[i+1]);solve();for(int i=1;i<=tot;i++)for(int j=0;j<(int)ed[i].size();j++) ans[ed[i][j]]+=cnt[i]/(spj[ed[i][j]]+1);for(int i=1;i<=m;i++) write(tp[i]>=0?n-tp[i]+1:ans[i]);return 0;
}
