TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1322
  • 問題
  • P1322【CEOI2003】赛车
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    審判説明 : 1s,64MB
    問題説明

    有n辆赛车,从各不相同的位置出发,以各种速度开始往右行驶,不断有超车现象发生,如下图所示。

    給定n辆赛车的出发位置Xi与速度Vi,请输出超车事件的总数,以及依序列出最早发生的超车事件。若有两个超车事件同時发生,请先输出超车位置数值较小的。为了怕危险,测试数据里面不会有两个超车事件同时同地发生。

    入力形式

    第一列有一个正整数N (1<=N<=250,000) ,第二列开始有N列,每列包含两个整数Xi和Vi代表第i辆车的初始位置与速度。(0<=Xi<=1,000,000,1<=Vi<=100)

    出力形式

    第一列请输出超车事件总数除以1,000,000的余数。

    第二列开始请依序输出超车事件。若全体的超车事件超过10,000个,那么只要输出前10,000个超车事件即可。   每一个超车事件可以用两个数字表示i, j,代表i超越j。

    サンプル入力

    4
    0 2
    2 1
    3 8
    6 3

    サンプル出力

    2
    3 4
    1 2

    ヒント

    对于30%的数据,n<=10
    对于40%的数据,n<=1000