← 返回题目列表

AtCoder · joisc2010_lake

lake. 湖

中文机器翻译题面 查看原题

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

湖 (Lake) - 原题 PDF 第 1 页
原题PDF第7页
湖 (Lake) - 原题 PDF 第 2 页
原题PDF第8页
可复制的 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