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

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


本文章由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θ,所以存下点积和叉积的约分后的形式即可。
需要注意的是,将一根直线翻折后如果还能匹配,会被匹配两次,所以要除以二。再就是对于共线和垂直的向量要特殊处理。

代码

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

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


HNCJ OIer