#5614. 超速检测
-
ID: 5614
Type: Default
1000ms
128MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
超速检测
说明
小D新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为L的南北主干道的车辆超速检测。为了考考小D，上司首先需要他解决一个简化的场景。 这个周末，主干道上预计出现n辆车，其中第i辆车从主干道上距离最南端$d _ { i }$的位置驶入，以$v _ { i }$的初速度和$a _ { i }$的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故$v _ { i } > 0 ,$，但$a _ { i }$可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为L的位置）或速度降为0（这只可能在$a _ { i } < 0$时发生）时，我们认为该车驶离主干道。 主干道上设置了m个测速仪，其中第j个测速仪位于主干道上距离最南端$ P_j $的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的瞬时速度超过了道路限速V，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。 上司首先想知道，如果所有测速仪都是开启的，那么这n辆车中会有多少辆车被判定为超速。 其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当n辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。 由于n很大，上司允许小D使用编程解决这两个问题，于是小D找到了你。 如果你对于加速度并不熟悉，小D贴心地在本题的“提示”部分提供了有关加速度的公式。输入格式
从文件detect.in中读入数据。 本题有多组测试数据。 输入的第一行包含一个正整数T，表示数据组数。 接下来包含T组数据，每组数据的格式如下： 第一行包含四个整数n,m,L,V,分别表示车辆数量、测速仪数量、主干道长度和道路限速。 接下来n行： 第i行包含三个整数$d _ { i } , v _ { i } , a _ { i }$描述一辆车。 最后一行包含m个整数$p _ { 1 } , p _ { 2 } , \cdots , p _ { m }$描述道路上所有测速仪的位置。输出格式
输出到文件 detect.out中。 对于每组数据：输出一行包含两个整数，第一个整数为所有测速仪都开启时被判定为超速的车辆数量，第二个整数为在不漏掉超速车辆的前提下最多可以关闭的测速仪数量。1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 ‐2
6 4 ‐4
2 5 8 9 15
3 3
提示
## 【样例 1 解释】
在该组测试数据中，主干道长度为15，限速为3，在距离最南端2,5,8,9,15的位置各设有一个测速仪。
·第一辆车在最南端驶入，以3的速度匀速行驶。这辆车在整个路段上都没有超速。
·第二辆车在距离最南端12的位置驶入，以4的速度匀速行驶。在最北端驶离主干道时，它会被距离最南端15的测速仪判定为超速。
·第三辆车在距离最南端1的位置驶入，以1的初速度、4的加速度行驶。其在行驶了$\frac { 3 ^ { 2 } - 1 ^ { 2 } } { 2 \times 4 } = 1$的距离，即到达2的位置时，速度变为3，并在之后一直超速。因此这辆车会被除了距离最南端2的测速仪以外的其他测速仪判定为超速。
·第四辆车在距离最南端5的位置驶入，以5的初速度、-2的加速度行驶。其在行驶了$\frac { 3 ^ { 2 } - 5 ^ { 2 } } { 2 \times ( - 2 ) } = 4$的距离，即到达9的位置时，速度变为3。因此这辆车在距离最南端[5,9)时超速，会被距离最南端5和8的两个测速仪判定为超速。
·第五辆车在距离最南端6的位置驶入，以4的初速度、-4的加速度行驶。在其行驶了$\frac { 3 ^ { 2 } - 4 ^ { 2 } } { 2 \times ( - 4 ) } = \frac { 7 } { 8 }$的距离后，即这辆车到达$6 \frac { 7 } { 8 }$的位置时，其速度变为3。因此
这辆车在距离最南端$[ 6 , 6 \frac { 7 } { 8 } )$时超速，但这段区间内没有测速仪，因此不会被判定为超速。
因此第二、三、四辆车会被判定为超速，输出的第一个数为3。
我们可以关闭距离最南端2,8,9的三个测速仪，保留5和15的两个测速仪，此时三辆之前被判定为超速的车依然被判定为超速。可以证明不存在更优方案，因此输出的第二个数为3。
【样例 2】
见选手目录下的 detect/detect2.in 与 detect/detect2.ans。
该组样例满足 n, m ≤ 10。
【样例 3】
见选手目录下的 detect/detect3.in 与 detect/detect3.ans。
该组样例满足特殊性质 A，其中前十组测试数据满足 n, m ≤ 3000。
【样例 4】
见选手目录下的 detect/detect4.in 与 detect/detect4.ans。
该组样例满足特殊性质 B，其中前十组测试数据满足 n, m ≤ 3000。
【样例 5】
见选手目录下的 detect/detect5.in 与 detect/detect5.ans。
该组样例满足特殊性质 C，其中前十组测试数据满足 n, m ≤ 3000。
特殊性质 A：保证 ai = 0。
特殊性质 B：保证 ai > 0。
特殊性质 C：保证 ai < 0，且所有车都不在最北端驶离主干道。
## 【提示】
与加速度有关的定义和公式如下：
·匀加速运动 是指物体在运动过程中，加速度保持不变的运动，即每单位时间内速度的变化量是恒定的。
·当一辆车的初速度为$v _ { 0 }$、加速度a≠0,，做匀加速运动，则t时刻后它的速度$v _ { 1 } = v _ { 0 } + a \times t ,$，它的位移（即行驶路程）$s = v _ { 0 } \times t + 0 . 5 \times a \times t ^ { 2 }$。
·当一辆车的初速度为$v _ { 0 }$、加速度a≠0，做匀加速运动，则当它的位移（即行驶路程）为s时，这辆车的瞬时速度为$\sqrt { v _ { 0 } ^ { 2 } + 2 \times a \times s } 。$
·当一辆车的初速度为$v _ { 0 } 、$加速度a≠0,，在它的位移（即行驶路程）为$\frac { v _ { 1 } ^ { 2 } - v _ { 0 } ^ { 2 } } { 2 a }$时，这辆车的瞬时速度为$v _ { 1 } 。$
如果你使用浮点数进行计算，需要注意潜在的精度问题。