/ Vijos / 题库 /

滑动输入法

滑动输入法

背景

Vijos因为某些原因闭站许久的这段时间内,管理团队们也走向了不同的地方创造新的奇迹。例如Vivian Snow神牛,就去开发了一款创新的输入法……

描述

Vivian Snow神牛开发的输入法,是一款划时代的输入法,更具体地说,是一款划时代的英文输入法——它不是通过按键来输入单词,而是通过划动来输入单词!
一般地来说,这个输入法会在手机屏幕上显示一个键盘,这个键盘有N个矩形区域,每个矩形区域代表一个字母;用户输入单词时,首先选择一个地方按下,然后在屏幕上划动自己的手指画出若干条连续的折线段,最后抬起手,完成单词的输入。

当然输入法后台的程序其实需要做许多的工作,其中之一就是根据用户的输入判断出用户想输入什么单词。我们不妨假设用户实际想“输入”的字母的位置都落在折线段的起点、终点及折点处(折点就是两条线段的交点)。当然,这个位置是有误差的,输入法会提供容差量R的设置,表示假如以起点、终点与折点为圆心画出一个半径为R的圆,与圆相切或相交的矩形区域的字母都是用户可能输入的字母。

假如折线段由线段l1, l2, ..., ln组成,我们定义用户的输入顺序为:起点,l1与l2的交点,l2与l3的交点,..., ln-1与ln的交点,终点。

现在请你重复Vivian Snow神牛的工作:对于给定的单词列表、折线段以及每个矩形对应的字母,求出用户可能输入的单词有哪些。

数据保证单词列表不会有重复的单词。

格式

输入格式

输入第一行有三个数N, M, W (1 <= N <= 20, 1 <= M <= 10, 1 <= W <= 10), 表示有N个矩形区域,M条线段,W个单词。

然后是一个整数R(0 <= R <= 50),表示容错阀值。

接下来是N行,每行四个整数x, y, a, b和一个字符c,表示矩形的左下角坐标和右上角坐标,以及它代表的字符。字符保证是大写、小写字母或者为数字。

接下来是M + 1行,每一行都是两个整数c, d,其中第一行为线段的起点,其他行中第i - 1行与第i行的两个坐标构成一条线段。

最后是W行,每一行都是一个长度不超过10的单词,单词只由大写、小写字母与数字组成,没有多余的空格。

数据保证所有坐标值的绝对值都小于2^30。

输出格式

输出第一行为用户可能输出的单词数Ans。

接下来的Ans行,每一行是一个用户可能输入的单词。

注意按字符串升序输出,例如A应该在B之前输出,a则应该在ZZZZ后面输出。

如果单词数为0,注意不要输出多余的空行。

样例1

样例输入1

5 3 2
0
0 0 1 1 A
1 1 2 2 B
2 2 3 3 C
3 3 4 4 D
4 4 5 5 E
0 0
1 1
2 2
3 3
CDE
ABCD

样例输出1

1
ABCD

限制

所有测试点每个点1秒。

信息

ID
1709
难度
8
分类
模拟 | 搜索 | 枚举 点击显示
标签
(无)
递交数
367
已通过
46
通过率
13%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Vijos复活邀请赛