#P9035. [2017年备战省选]隐形斗篷

    ID: 9241 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-扫描线普通线段树倍增跳转二分查找事件同坐标排序坐标变换

[2017年备战省选]隐形斗篷

题目描述

在边长为 mm 的正方形 [0,m]×[0,m][0,m]\times[0,m] 中,每个人从一个整数坐标出发,沿横向或纵向直线行走。行走速度为每单位时间一单位距离,且不能主动改变方向。

正方形内有 nn 个箭头,每个箭头是从 (x1,y1)(x_1,y_1) 指向 (x2,y2)(x_2,y_2) 的水平或竖直线段。人一接触箭头就将行走方向改为该箭头指向的方向。接触箭头的任一点都生效,包括出发时已在线段上或经过线段端点的情况。走到箭头的终点后,仍沿当前方向行走,直到遇到下一支箭头、走出正方形或时间用完。

每个人的起点、初始方向和行走时间独立给定,人与人互不影响。若时间用完时仍在正方形内,求此时的坐标。若已离开正方形,输出离开之前在正方形中的最后一个坐标。

输入格式

第一行两个整数 n,mn,m。

接下来 nn 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,描述一个箭头的起点和终点。

接下来一行一个整数 qq,表示人数。其后 qq 行,每行依次为两个整数 x,yx,y、一个字符 chch 和一个整数 TT,分别表示起点坐标、初始方向和行走时间。

输出格式

按输入顺序输出 qq 行,每行两个整数,表示该人的终点坐标或离开前的最后一个坐标。

样例

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

数据范围

对于全部数据,1≤n,m,q≤1051\le n,m,q\le 10^5,0≤x1,y1,x2,y2,x,y≤m0\le x_1,y_1,x_2,y_2,x,y\le m,0≤T≤10150\le T\le 10^{15}。

方向字符 L、R、D、U 分别表示方向向量 (−1,0)(-1,0)、(1,0)(1,0)、(0,−1)(0,-1)、(0,1)(0,1)。

本站评测保证每个箭头的起点和终点不同,任意两个箭头的闭线段都没有公共点。

原赛采用捆绑测试。第 1 个子任务 10 分,满足 n,m,q≤10n,m,q\le 10。第 2 个子任务 20 分,满足 n,m,q,T≤1000n,m,q,T\le 1000。第 3 个子任务 70 分,使用完整范围。

原始题面见 3.pdf。