Lake(湖) - joi2010-day4

出典: 第9回日本情報オリンピック 春季トレーニング合宿

時間制限: 1秒

メモリ制限: 256MB

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

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

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

課題(TASK)

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

制限(CONSTRAINTS)

1 ≤ N ≤ 2,000	計画の数
0 ≤ s[i] < 500,000, 0 ≤ t[i] ≤ 500,000	地点の座標

入力(INPUT)

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

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

出力(OUTPUT)

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

採点基準(GRADING)

40点分のテストグループにおいて, N ≤ 200 である.

入出力例(EXAMPLE)

入力例(Sample Input)	出力例(Sample Output)
5 50000 150000 450000 100000 200000 300000 260000 350000 0 230000	3