#3673. [USACO13OPEN] Cow Race G

[USACO13OPEN] Cow Race G

题目描述

为了最终解决谁跑得更快的长期争论,Bessie和她的朋友Elsie决定在农场举行一场赛跑。

两头奶牛从同一地点同时出发,朝同一方向奔跑。每头奶牛的跑步过程由多个"阶段"组成,每个阶段中奶牛保持恒定速度奔跑。例如,Bessie可能先以速度5跑3个单位时间,然后以速度10跑6个单位时间。两头奶牛跑步的总时间相同。

奶牛们希望你能帮助计算比赛过程中领先地位变化的次数。当满足以下条件时记为一次领先变化:

  1. 奶牛A超越奶牛B成为领先者
  2. 上一次领先的奶牛是B

特别地,如果B原本领先,A先与B齐头并进一段时间后再超越,这也算作一次领先变化。

输入格式

第一行:两个空格分隔的整数N和M(1 ≤ N, M ≤ 1000),分别表示Bessie和Elsie的跑步阶段数。

接下来N行:每行描述Bessie的一个跑步阶段,包含两个整数(速度和时间,范围1-1000)。

随后M行:每行描述Elsie的一个跑步阶段,包含两个整数(速度和时间,范围1-1000)。

输出格式

一个整数,表示比赛过程中领先地位变化的次数。

输入输出样例

输入 #1

4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9

输出 #1

2

样例解释

Bessie的跑步阶段:

  1. 速度1跑2单位时间
  2. 速度4跑1单位时间
  3. 速度1跑1单位时间
  4. 速度2跑10单位时间

Elsie的跑步阶段:

  1. 速度2跑3单位时间
  2. 速度1跑2单位时间
  3. 速度3跑9单位时间

比赛过程:

  • 前3单位时间Elsie领先(双方都跑了6单位距离)
  • 第4单位时间Bessie短暂领先(第一次领先变化)
  • 随后Elsie重新领先(第二次领先变化)
  • 最终Elsie保持领先

因此输出结果为2次领先变化。