24125번 - 湖 (Lake) 다국어

カナダの南東部，アメリカとの国境の場所には，「五大湖」として知られる有名な 5 つの湖がある．この たびカナダで IOI が開催されるのに伴い，会場にもっとも近いオンタリオ湖に観光船を運航する計画がい くつも持ち上がった．

おのおのの観光船の計画は，湖の外周の 2 点を結ぶものであり，計画は全部で N 個ある．i 個目の計画 は，地点 s_i と地点 t_i を結ぶ観光船を運航するというものである．ここで，地点 x とは，湖の東の端から周 に沿って反時計回りに距離 x メートルだけ進んだ地点のことを指す．湖の一周の長さは 500,000 メートル である．

これらの中からできるだけ多くの計画を実現させたいが，船同士の衝突を避けるため，2 つの航路が交 差してはならない．

N 個の運航計画が与えられたとき，実現できる計画の個数の最大値を求めるプログラムを作成せよ．

標準入力から以下の入力を読み込め．

• 入力の 1 行目には整数 N が書かれている．これは，観光船を運航する計画の個数を表す．
• 入力の i + 1 行目 (1 ≤ i ≤ N) には 2 つの整数 s_i, t_i が空白を区切りとして書かれている. これらは, i 番目の計画で結ばれる予定である 2 つの地点を表す．s₁, . . . , s_N, t₁, . . . , t_N の計 2N 個の値はすべて異 なる．

標準出力に，与えられた運航計画のうち，実現できる計画の個数の最大値を表す 1 つの整数を出力せよ．

• 1 ≤ N ≤ 2, 000 計画の数
• 0 ≤ s_i < 500, 000，0 ≤ t_i < 500, 000 地点の座標

上の入力例における 5 つの計画を表した図 (地点間の間隔は正確ではない)．太線の 3 つの計画を選べば航 路が交差することなく船を運航できる．