[BZOJ1039/Luogu2603][ZJOI2008]无序运动Movement(AC自动机,计算几何)

发布于 2018-03-21  82 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1039/Luogu2603][ZJOI2008]无序运动Movement(AC自动机,计算几何)

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)

Tag

AC自动机,计算几何

解决思路

这题的关键其实不是在于 AC 自动机,而是如何把模型转化到 AC 自动机上。
考虑把一条折线不管怎么经过上述变换,哪些信息是不会变的。可以知道是相邻两向量的模长之比和夹角。
那么可以记录这些信息,并化为最简形式,然后就可以在 AC 自动机上进行匹配了。
为了避免精度问题,可以把记录模长之比改为记录模长的平方之比,而夹角的计算可以分别计算两向量的点积和叉积,它们之比就是tanθ,所以存下点积和叉积的约分后的形式即可。
需要注意的是,将一根直线翻折后如果还能匹配,会被匹配两次,所以要除以二。再就是对于共线和垂直的向量要特殊处理。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1600100;
const int inf=2147483647;

int gcd(int a,int b)
{
    int t;
    while (b) t=a,a=b,b=t%b;
    return a;
}

class Point
{
public:
    int x,y;
    Point(){
        x=y=0;return;
    }
    Point(int a,int b){
        x=a;y=b;return;
    }
    int len(){
        return x*x+y*y;
    }
};

Point operator + (Point A,Point B){
    return (Point){A.x+B.x,A.y+B.y};
}

Point operator - (Point A,Point B){
    return (Point){A.x-B.x,A.y-B.y};
}

int operator * (Point A,Point B){//点积
    return A.x*B.x+A.y*B.y;
}

int operator ^ (Point A,Point B){//叉积
    return A.x*B.y-A.y*B.x;
}

class Data//AC自动机中的元素
{
public:
    int len1,len2,dot,cross;//记录四种信息,两个向量的长度平方,点积,叉积
    Data(){
        len1=len2=dot=cross=0;
    }
    Data(int l1,int l2,int dt,int cs){
        int t=gcd(abs(l1),abs(l2));
        len1=l1/t;len2=l2/t;dot=dt;cross=cs;
        if (dt==0) cross=(cs<0)?(-1):(1);//点积为0,说明两向量垂直
        else if (cs==0) dot=(dt<0)?(-1):(1);//叉积为0,说明两向量共线
        else
        {
            t=gcd(abs(dt),abs(cs));
            dot=dt/t;cross=cs/t;
        }
        return;
    }
};
//因为要在AC自动机中匹配,所以定义好比较的方式
bool operator < (Data A,Data B)
{
    if (A.len1!=B.len1) return A.len1<B.len1;
    if (A.len2!=B.len2) return A.len2<B.len2;
    if (A.dot!=B.dot) return A.dot<B.dot;
    return A.cross<B.cross;
}

bool operator == (Data A,Data B){
    return ((A.len1==B.len1)&&(A.len2==B.len2)&&(A.dot==B.dot)&&(A.cross==B.cross));
}

bool operator != (Data A,Data B){
    return !(A==B);
}

class Trie
{
public:
    int fail,id;
    Data D;
    map<Data,int> Son;
};

int n,m,nodecnt,pcnt;
int Len[maxN];
Data P[maxN];
Point Input[maxN];
Trie T[maxN];
bool Same[maxN];//标记某一个是否为一根直线
int idcnt=0,Id[maxN],Queue[maxN],Cnt[maxN];

void GetFail();
void AhoCorasick();

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)//输入数据库中的直线
    {
        scanf("%d",&Len[i]);
        for (int j=1;j<=Len[i];j++) scanf("%d%d",&Input[j].x,&Input[j].y);
        if (Len[i]<=2) continue;//对于点数只有二及一下的折线,在后面可以直接得到答案
        Same[i]=1;
        for (int j=2;j<Len[i];j++)
        {
            Point p1=Input[j]-Input[j-1],p2=Input[j+1]-Input[j];
            P[++pcnt]=Data(p1.len(),p2.len(),p1*p2,p1^p2);
            if ((p1^p2)!=0) Same[i]=0;
        }
    }
    //转化成AC自动机中的数据
    for (int i=1,p=1;i<=m;i++)
        if (Len[i]>2)
        {
            int now=0;
            for (int j=1;j<=Len[i]-2;j++,p++)
            {
                if (T[now].Son.count(P[p])==0) T[now].Son[P[p]]=++nodecnt;
                now=T[now].Son[P[p]];
            }
            if (T[now].id==0) T[now].id=++idcnt;
            Id[i]=T[now].id;
        }
    //构建Fail指针
    GetFail();
//输入待匹配的串
    for (int i=1;i<=n;i++) scanf("%d%d",&Input[i].x,&Input[i].y);
//将待匹配串构建成需要的形式
    pcnt=0;
    for (int i=2;i<n;i++)
    {
        Point p1=Input[i]-Input[i-1],p2=Input[i+1]-Input[i];
        P[++pcnt]=Data(p1.len(),p2.len(),p1*p2,p1^p2);
    }
//先正着匹配一遍
    AhoCorasick();
    //再把直线上下翻折再匹配一遍
    for (int i=1;i<=pcnt;i++) P[i].cross=-P[i].cross;
    AhoCorasick();

    for (int i=1;i<=m;i++)
        if (Len[i]<=2) printf("%d\n",n-Len[i]+1);
        else
        {
            if (Same[i]) printf("%d\n",Cnt[Id[i]]/2);//注意是直线的情况
            else printf("%d\n",Cnt[Id[i]]);
        }

    return 0;
}

void GetFail()
{
    int h=0,t=0;
    for (map<Data,int>::iterator i=T[0].Son.begin();i!=T[0].Son.end();i++) Queue[++h]=i->second;
    while (t!=h)
    {
        int u=Queue[++t];
        for (map<Data,int>::iterator i=T[u].Son.begin();i!=T[u].Son.end();i++)
        {
            Data key=i->first;int id=i->second;
            int p=T[u].fail;
            while ((p)&&(T[p].Son.count(key)==0)) p=T[p].fail;
            if (T[p].Son.count(key)!=0) T[id].fail=T[p].Son[key];
            Queue[++h]=id;
        }
    }
    return;
}

void AhoCorasick()
{
    int now=0;
    for (int i=1;i<=pcnt;i++)
    {
        if (T[now].Son.count(P[i])!=0) now=T[now].Son[P[i]];
        else
        {
            while ((now)&&(T[now].Son.count(P[i])==0)) now=T[now].fail;
            if (T[now].Son.count(P[i])!=0) now=T[now].Son[P[i]];
        }
        int p=now;
        while (p)
        {
            Cnt[T[p].id]++;
            p=T[p].fail;
        }
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1039/Luogu2603][ZJOI2008]无序运动Movement(AC自动机,计算几何)


HNCJ OIer