#ñ. 【基础】飞船赛
【基础】飞船赛
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老生预选赛
- 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