[CEOI2003] The Race
题目描述
在一年一度的调谐宇宙飞船星际竞赛中,$N$ 艘宇宙飞船将参赛。每艘宇宙飞船 $i$ 的调谐方式都是这样的,它可以在零时间内加速到它的最大速度 $V_i$ 并继续以那个速度巡航。由于过去的成就,每艘宇宙飞船都从一个起始位置出发,给定其飞船离起跑线的距离。
赛程无限长。因为宇宙飞船速度很快,比赛的路线一直都是笔直的。在直线赛道上,飞船可以很容易地相互通过,而没有互相干扰。
很多观众还没有意识到,比赛的胜负是可以提前预测的。你的任务是向他们展示这一点,告诉他们宇宙飞船将相互经过多少次,并通过按时间顺序预测宇宙飞船经过的前 $10000$ 次。
您可以假设每艘宇宙飞船都从不同的位置开始。此外,任何时候在赛道的同一位置上永远不会有超过两艘飞船。
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/437urrvu.png)
输入输出格式
输入格式
第一行包含一个整数 $N$ 指定了正在竞争的飞船的数量。接下来的 $N$ 行中的每一行都描述了一艘宇宙飞船的特性。第 $i+1$ 行用两个整数 $X_i$ 和 $V_i$ 描述第 $i$ 艘飞船,表示第 $i$ 艘飞船的起始位置和速度。飞船按照起始位置排序,即 $X_1 < X_2 < \cdots < X_N$。 起始位置是飞船开始的起点线后的公里数,速度以千米每秒为单位。
输出格式
第一行应该包含一个整数为飞船在比赛中相互通过的次数,并对 $1000000$ 取模。接下来的每一行都应该按时间顺序表示一个经过。如果要通过 $10000$ 次以上,只输出前 $10000$ 次。如果小于 $10000$ 次,输出所有的次。每一行应该由两个整数 $i$ 和 $j$ 组成,指定飞船 $i$ 经过飞船 $j$。如果多次相互通过同时发生,它们必须按此次赛道位置排序。这意味着发生在起跑线附近的相互通过必须首先列出。路过的时间是两艘宇宙飞船在同一位置的时间
输入输出样例
输入样例 #1
4
0 2
2 1
3 8
6 3
输出样例 #1
2
3 4
1 2
说明
#### 数据规模与约定
对于 $100 \%$ 的数据,$0 < N \leq 250 000$,$0 \leq X_i \leq 1 000 000$,$0 < V_i < 100$。
#### 题目说明
来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2003 的 [The Race](https://www.ceoi2003.de/www/downloads/therace-en.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。