User's AC Ratio

83.3% (10/12)

Submission's AC Ratio

21.8% (17/78)

Description

有n輛賽車,從各不相同的位置出發,以各種速度開始往右行駛,不斷有超車現象發生,如下圖所示。

給定n輛賽車的出發位置Xi與速度Vi,請輸出超車事件的總數,以及依序列出最早發生的超車事件。
若有兩個超車事件同時發生,請先輸出超車位置數值較小的。
為了怕危險,你和滷肉保證測試資料裡面不會有兩個超車事件同時同地發生。

Input Format

第一列有一個正整數N (0< N <=250,000)
第二列開始有N列,每列包含兩個整數Xi和Vi代表第i輛車的初始位置與速度。
(0<=Xi<=1,000,000,0<Vi<=100,並且Xi依照嚴格遞增順序排列)

Output Format

第一列請輸出超車事件總數除以1,000,000的餘數

第二列開始請依序輸出超車事件。若全體的超車事件超過10,000個,那麼只要輸出前10,000個超車事件即可。
每一個超車事件可以用兩個數字表示i, j,代表i超越j。

Sample Input

4
0 2
2 1
3 8
6 3

Sample Output

2
3 4
1 2

Hints

Problem Source

原TIOJ1403 / 快樂暑假營第四次練習比賽。Problem Setter:Tmt。
(Adapted From CEOI2003 The Race, 算法藝術P.89)

Subtasks

For Testdata: 0 ~ 0, Score: 8
For Testdata: 1 ~ 1, Score: 8
For Testdata: 2 ~ 2, Score: 8
For Testdata: 3 ~ 3, Score: 8
For Testdata: 4 ~ 4, Score: 8
For Testdata: 5 ~ 5, Score: 8
For Testdata: 6 ~ 6, Score: 8
For Testdata: 7 ~ 7, Score: 8
For Testdata: 8 ~ 8, Score: 8
For Testdata: 9 ~ 9, Score: 8
For Testdata: 10 ~ 10, Score: 8
For Testdata: 11 ~ 11, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 65536 262144
1 900 65536 262144
2 900 65536 262144
3 900 65536 262144
4 900 65536 262144
5 900 65536 262144
6 900 65536 262144
7 900 65536 262144
8 900 65536 262144
9 900 65536 262144
10 900 65536 262144
11 900 65536 262144