#P9035. [2017年备战省选]隐形斗篷
[2017年备战省选]隐形斗篷
题目描述
在边长为 的正方形 中,每个人从一个整数坐标出发,沿横向或纵向直线行走。行走速度为每单位时间一单位距离,且不能主动改变方向。
正方形内有 个箭头,每个箭头是从 指向 的水平或竖直线段。人一接触箭头就将行走方向改为该箭头指向的方向。接触箭头的任一点都生效,包括出发时已在线段上或经过线段端点的情况。走到箭头的终点后,仍沿当前方向行走,直到遇到下一支箭头、走出正方形或时间用完。
每个人的起点、初始方向和行走时间独立给定,人与人互不影响。若时间用完时仍在正方形内,求此时的坐标。若已离开正方形,输出离开之前在正方形中的最后一个坐标。
输入格式
第一行两个整数 。
接下来 行,每行四个整数 ,描述一个箭头的起点和终点。
接下来一行一个整数 ,表示人数。其后 行,每行依次为两个整数 、一个字符 和一个整数 ,分别表示起点坐标、初始方向和行走时间。
输出格式
按输入顺序输出 行,每行两个整数,表示该人的终点坐标或离开前的最后一个坐标。
样例
3 3
0 0 0 1
0 2 2 2
3 3 2 3
12
0 0 L 0
0 0 L 1
0 0 L 2
0 0 L 3
0 0 L 4
0 0 L 5
0 0 L 6
2 0 U 2
2 0 U 3
3 0 U 5
1 3 D 2
1 3 R 2
0 0
0 1
0 2
1 2
2 2
3 2
3 2
2 2
3 2
1 3
2 2
1 3
数据范围
对于全部数据,,,。
方向字符 L、R、D、U 分别表示方向向量 、、、。
本站评测保证每个箭头的起点和终点不同,任意两个箭头的闭线段都没有公共点。
原赛采用捆绑测试。第 1 个子任务 10 分,满足 。第 2 个子任务 20 分,满足 。第 3 个子任务 70 分,使用完整范围。
原始题面见 3.pdf。