lake - 湖 (Lake) Editorial /

Time Limit: 1 sec / Memory Limit: 256 MiB

AtCoder での提出方法

入力は標準入力から読み込み,出力は標準出力に行うこと.

配点 : 100 点

問題文

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

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

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

課題

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

制約

  • 1 \leqq N \leqq 2{,}000:計画の数.
  • 0 \leqq s_i < 500{,}000,0 \leqq t_i < 500{,}000:地点の座標.

入力

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

  • 入力の 1 行目には整数 N が書かれている.これは,観光船を運航する計画の個数を表す.
  • 入力の i + 1 行目 (1 \leqq i \leqq N) には 2 つの整数 s_{i},t_{i} が空白を区切りとして書かれている. これらは,i 番目の計画で結ばれる予定である 2 つの地点を表す.s_1, \ldots, s_N, t_1, \ldots, t_N の計 2N 個の値はすべて異なる.

出力

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

採点基準

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

入力例 1

5
50000 150000
450000 100000
200000 300000
260000 350000
0 230000

出力例 1

3
2010-lake-example.png

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


Source Name

JOI 2009-2010 春季トレーニング合宿 Contest Day4