以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 4 - Lake
湖(Lake)
カナダの南東部,アメリカとの国境の場所には,「五大湖」として知られる有名な5 つの湖がある.この
たびカナダでIOI が開催されるのに伴い,会場にもっとも近いオンタリオ湖に観光船を運航する計画がい
くつも持ち上がった.
おのおのの観光船の計画は,湖の外周の2 点を結ぶものであり,計画は全部でN 個ある.i 個目の計画
は,地点si と地点ti を結ぶ観光船を運航するというものである.ここで,地点x とは,湖の東の端から周
に沿って反時計回りに距離x メートルだけ進んだ地点のことを指す.湖の一周の長さは500,000 メートル
である.
これらの中からできるだけ多くの計画を実現させたいが,船同士の衝突を避けるため,2 つの航路が交
差してはならない.
課題(TASK)
N 個の運航計画が与えられたとき,実現できる計画の個数の最大値を求めるプログラムを作成せよ.
制限(CONSTRAINTS)
1 ≦N ≦2, 000 計画の数
0 ≦si < 500, 000,0 ≦ti < 500, 000 地点の座標
入力(INPUT)
標準入力から以下の入力を読み込め.
• 入力の1 行目には整数N が書かれている.これは,観光船を運航する計画の個数を表す.
• 入力のi + 1 行目(1 ≦i ≦N) には2 つの整数si, ti が空白を区切りとして書かれている. これらは, i
番目の計画で結ばれる予定である2 つの地点を表す.s1, . . . , sN, t1, . . . , tN の計2N 個の値はすべて異
なる.
出力(OUTPUT)
標準出力に,与えられた運航計画のうち,実現できる計画の個数の最大値を表す1 つの整数を出力せよ.
採点基準(GRADING)
40 点分のテストグループにおいて,N ≦200 である.
Page 1 of 2
Japanese Olympiad In Informatics 2009/2010
Spring Training Camp
March 19 - 25, 2010, Komaba/Yoyogi, Tokyo
Contest day 4 - Lake
入出力例(EXAMPLE)
入力例(Sample Input) 出力例(Sample Output)
5 3
50000 150000
450000 100000
200000 300000
260000 350000
0 230000
150000 100000
200000
50000
230000
0
260000
450000
300000
350000
上の入力例における5 つの計画を表した図(地点間の間隔は正確ではない).太線の3 つの計画を選べば航
路が交差することなく船を運航できる.
Page 2 of 2