ñ. 【基础】飞船赛

    Type: Default 1000ms 16MiB

【基础】飞船赛

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

有N(1<=N<=)个飞船进行比赛,它们的跑道为直线并互相平行。他们有一条共同的起跑线,但第i个飞船从起跑线后Xi处开始比赛(Xi各不相同),比赛开始后,它能在零时间内加速到最大速度Vi并永远保持此速度。比赛没有终点,即会永远进行下去。

你的任务是算出一共有多少次“超车”,并按时间顺序输出前10000次。保证在同一时刻不会有两个以上的飞船位于同一位置。

输入格式

第1行:N(0<=N<=250000)

第(i+1)行:Xi和Vi(0<=Xi<=1000000 0<Vi<100)

后N行是Xi按升序排列的。

输出格式

第1行:“超车”次数(保证不超过1000000,?或在此数量级上)。

接下来按时间顺序每行输出i和j,表示第i个飞船超过第j个飞船。若两次超车在同一时刻发生,则按“超车”地点与起跑线的距离由小到大排序。

若“超车”次数大于10000,则输出前10000次,否则输出全部。

样例

4
0 2
2 1
3 8
6 3
2
3 4
1 2

提示

50%的数据  n<=100 m<=150

100%的数据 n<=100000 m<=200000 xi<=100000000 vi<=100

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45