问题 5140 --赛车

5140: 赛车

题目描述

小爱和她的朋友小艾正在进行赛车游戏。她们从同一个起点,同一方向,同时出发。每个人在比赛中的速度可以被分为若干个**阶段**。在每个**阶段**里,小爱或小艾的速度是不变的。 由于车手的速度有变化,会出现**超车**的现象。所谓**超车**,就是指原本位置落后的一人,通过较快的速度实现了位置的超前。判定是否**超车**,关键看两人的相对位移是否从正变负(或从负变正)。在起点位置,因两人相对位置只是从 $0$ 变成了正数,所以不算发生**超车**。 给定小爱和小艾在每个**阶段**的速度和持续时间,请统计一下,在比赛的过程中,出现了多少次**超车**现象。

输入

第一行:两个整数 $n$ 和 $m$ + $n$ 表示小爱的赛车进程分为 $n$ 个阶段; + $m$ 表示小艾的赛车进程分为 $m$ 个阶段。 接下来 $n$ 行:每行表示小爱进程中的一个阶段,有两个整数 $t_i$ 和 $v_i$,表示该阶段中,小爱的速度为 $v_i$,持续时间为 $t_i$。 接下来 $m$ 行:每行表示小艾进程中的一个阶段,有两个整数 $s_i$ 和 $w_i$,表示该阶段中,小艾的速度为 $w_i$,持续时间为 $s_i$。 保证两人赛车的总距离是相等的,即保证 $$v_1t_1+v_2t_2+\cdots+v_nt_n=w_1s_1+w_2s_2+\cdots+w_ms_m$$

输出

单个整数:表示在整个比赛过程中,共计出现了多少次超车**现象**。

样例输入输出

输入#1 复制
2 3
10 10
2 50
4 15
8 15
1 20
输出#1 复制
1

提示

记 $L=v_1t_1+v_2t_2+\cdots+v_nt_n$, + 对于 $30\%$ 的数据,$1\leq n, m\leq 100$,$1\leq L\leq 10000$; + 对于 $60\%$ 的数据,$1\leq n, m\leq 1000$,$1\leq L\leq 10^7$; + 对于 $100\%$ 的数据,$1\leq n, m\leq 10^5$,$1\leq L\leq 10^9$;
序号 标题 作者 发表时间 费用 订购数 操作