bzoj#P4223. Tourists
Tourists
题目描述
位于 Ultima Thule 的公园内的一条双重观光道路是由以下原理工作:
- 我们引入直角坐标系。
- 在一些时刻会有 个游客同时从点 和 出发(去散步)。其中第一个人出发点 ,第二个人出发点为 。
- 每一对游客都以相同的速度 行动(每秒前进单位长度)。第一个人沿直线 ,第二个人沿直线 行动。他们都向 轴正方向移动。
- 在一些时刻墙会出现。墙 是一条在点 和 之间的线段。每个墙都瞬间出现。
Ultima Thule 官方想要了解对于每一对同时出发的游客,他们将会有多长时间无法彼此望见?两个游客不能看到对方当且仅当他们位置的连线与至少一面墙相交。两条线段相交是指他们至少有一个公共点。我们假定线段的端点属于这条线段。
帮助他们计算所要求的时间。注意墙可以相交(以任何方式)或重合。
输入格式
第一行包含两个空格隔开的整数 ——游客的对数和墙的数目。
接下来 行每行三个空格隔开的整数 ——墙的两端和出现的时间。
最后一行包含 个严格递增、空格隔开的整数 ——每对游客出发的时刻。
输出格式
对每对游客输出一行一个整数——这对游客不能相互看见的时间是几秒。按照读入游客出发时间的顺序输出答案。
样例 #1
2 2
1 4 3
3 6 5
0 1
2
4
样例 #2
3 3
0 3 4
0 1 2
2 4 0
1 3 4
2
4
4
数据规模与约定
对于 的数据:,,,。