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




可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Fences
柵(Fences)
JOI 氏は,IOI 国に広大な土地を所有している.IOI 国の土地は座標平面として表され,直交するX 軸と
Y 軸が設定されている.X 座標がx,Y 座標がy の点を(x, y) で表す.JOI 氏の所有している土地は,X 座
標,Y 座標がいずれも−10100 以上10100 以下の領域である.この土地のうち,X 座標,Y 座標がいずれも
−S 以上S 以下の領域は牧草地であり,牛を飼育している.
JOI 氏は,牛が逃げ出さないように,牧草地をいくつかの柵で囲うことにした.いずれの柵の形状も,正
の実数の長さをもつ線分で表される.ここで,牧草地を柵で囲うとは,牧草地の内部のどの点からも,柵
が存在するような地点(このような地点としては,柵の端点も含むことに注意せよ) を通ることなく,JOI
氏の土地の外側へ行くことが不可能であるようにすることを意味する.JOI 氏の土地には最初からいくつ
かの柵が置いてあるので,それを使って囲ってもよい.これらの柵は,どの2 つの柵についても,それら
が共有点をもつならば,その点は少なくとも片方の柵の端点であるように置かれている.
JOI 氏は,柵を新たにいくらでも置くことができる.このとき,牧草地の内部や,JOI 氏の土地の外側を
通るように柵を置いてはいけないが,牧草地の境界を通るように柵を置くのはかまわない.この条件を満
たす限り,どのような長さの柵をどのような方向に置いてもかまわない.長さl (l > 0) の柵を1 個追加す
るためには,コストがl かかる.ここで,柵同士が交差したり,柵の端点が他の柵の端点と一致したりし
てもよい.また,柵の端点が他の柵上にあってもかまわない.
JOI 氏は,できるだけ少ないコストで,牧草地を柵で囲おうとしている.
課題
JOI 氏の牧草地の大きさと,最初から置かれている柵の情報が与えられたとき,牧草地を柵で囲うため
に必要なコストの総和の最小値を求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
• 1 行目には2 個の整数N, S が空白を区切りとして書かれている.これらは牧草地がX 座標,Y 座標
がいずれも−S 以上S 以下の領域であり,JOI 氏の所有している土地には最初N 個の柵が設置して
あることを表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N)には4 個の整数Ai, Bi, Ci, Di が空白を区切りとして書かれて
いる.これはi 番目の柵が,2 つの地点(Ai, Bi) および(Ci, Di) を結ぶ線分であることを表す.
出力
牧草地を柵で囲うために必要なコストの総和の最小値を1 行で出力せよ.出力する小数点以下の桁数に
ついての制限はないが,正解との絶対誤差は0.01 以下でなければならない.
柵– 1 / 4
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Fences
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦100.
• 1 ≦S ≦200.
• −200 ≦Ai ≦200 (1 ≦i ≦N).
• −200 ≦Bi ≦200 (1 ≦i ≦N).
• −200 ≦Ci ≦200 (1 ≦i ≦N).
• −200 ≦Di ≦200 (1 ≦i ≦N).
• (Ai, Bi) , (Ci, Di) (1 ≦i ≦N).
• 入力で与えられるどの柵も,牧草地の内部を通らない.
• 入力で与えられる異なる2 つの柵が共有点をもつならば,その点は少なくとも片方の柵の端点である.
小課題
この課題では小課題は全部で3 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [18 点]
• N = 1.
小課題2 [33 点]
• N ≦6.
小課題3 [49 点]
追加の制限はない.
柵– 2 / 4
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Fences
入出力例
入力例1 出力例1
3 4 29.0000000000
-3 5 1 8
-4 3 -4 6
5 1 7 2
入力例1 では,最初下左図のように柵が置かれている.ここで,中央の点線で示した正方形は,牧草地
の外周を表す.
この入力例では,下右図の細線で示したように新たな柵を置くと,牧草地を囲うことができる.このと
き,柵のコストは29 であり,これが最小値である.なお,この入力例の場合,29.0000000000 以外にも,
例えば29 や28.999 と出力しても正解と判定される.
y y
(1, 8) (1, 8)
(−4, 6) (−4, 6)
(−3, 5) (−3, 5) (4, 4) (4, 4)
(−4, 3) (−4, 3)
(7, 2) (7, 2)
(5, 1) (5, 1)
O O x x
(−4, −4) (4, −4) (−4, −4) (4, −4)
入力例2 出力例2
1 2 16.0000000000
-3 -3 -3 -2
すでに置かれている柵をまったく使わずに牧草地を囲んでも良いことに注意せよ.
入力例3 出力例3
4 3 14.1392801789
4 -1 3 4
-4 2 -2 4
-4 0 -5 6
0 -6 5 -2
柵– 3 / 4
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Fences
入力例4 出力例4
10 80 238.4778364511
175 95 60 -146
-106 57 18 185
190 -68 177 -142
84 -195 127 -179
34 143 126 69
-92 133 -190 80
-157 -66 -119 -161
-85 -124 129 -171
141 181 175 175
107 -38 150 148
柵– 4 / 4