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






可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 1 – IOI Fever
IOI 熱の感染拡大(IOI Fever)
JOI 国はxy 座標平面として表される.JOI 国にはN 軒の家があり,家には1 からN までの番号が付けら
れている.家i (1 ≦i ≦N) は座標(Xi, Yi) にあり,同じ座標に複数の家は存在しない.また,各家には1 人
の国民が住んでおり,家i に住んでいる国民を国民i と表す.今,JOI 国では大型連休が始まろうとしてい
る.時刻0 になるとすべての国民は同時に家を出発し,旅行を始める.最初に,各国民は「東」「西」「南」
「北」のうちいずれかの方向を選択し,以下の通りに動く.
• 国民i が「東」を選択した場合:x 軸の正の方向に速さ1 で動く.つまり,時刻t (t ≧0) における国
民i の座標は(Xi + t, Yi) となる.
• 国民i が「西」を選択した場合:x 軸の負の方向に速さ1 で動く.つまり,時刻t (t ≧0) における国
民i の座標は(Xi −t, Yi) となる.
• 国民i が「南」を選択した場合:y 軸の負の方向に速さ1 で動く.つまり,時刻t (t ≧0) における国
民i の座標は(Xi, Yi −t) となる.
• 国民i が「北」を選択した場合:y 軸の正の方向に速さ1 で動く.つまり,時刻t (t ≧0) における国
民i の座標は(Xi, Yi + t) となる.
残念なことに,時刻0 に国民1 が新型の感染症であるIOI 熱に感染してしまった.時刻0 において,国
民1 以外には感染者はいない.IOI 熱は国民の間で次のように伝染する.
ある時刻において国民a (1 ≦a ≦N) と国民b (1 ≦b ≦N) が同じ座標に存在し,その時点で国民a
が感染者で国民b が非感染者であった場合,国民b が新たに感染する.
これ以外の方法で新たな感染者が発生することはない.また,IOI 熱は不治の病であるため,感染者は二度
と非感染者になることはない.
JOI 国の大臣であるあなたは,国民が最悪な方向を選択した場合,何人の国民がIOI 熱に感染するかを見
積もらなければならない.
家の軒数と各家の座標が与えられたとき,時刻10100 における感染者数としてあり得る最大値を求めるプ
ログラムを作成せよ.
IOI 熱の感染拡大– 1 / 6
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 1 – IOI Fever
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N
X1 Y1
...
XN YN
出力
標準出力に,時刻10100 における感染者数としてあり得る最大値を1 行で出力せよ.
制約
• 1 ≦N ≦100 000.
• 0 ≦Xi ≦500 000 000 (1 ≦i ≦N).
• 0 ≦Yi ≦500 000 000 (1 ≦i ≦N).
• (Xi, Yi) , (Xj, Yj) (1 ≦i < j ≦N).
小課題
1. (5 点) N ≦7,Xi , Xj (1 ≦i < j ≦N),Yi , Y j (1 ≦i < j ≦N).
2. (8 点) N ≦15,Xi , Xj (1 ≦i < j ≦N),Yi , Yj (1 ≦i < j ≦N).
3. (6 点) N ≦100,Xi , Xj (1 ≦i < j ≦N),Yi , Yj (1 ≦i < j ≦N),X1 = 0,Y1 = 0.
4. (6 点) N ≦100,Xi , Xj (1 ≦i < j ≦N),Yi , Yj (1 ≦i < j ≦N).
5. (12 点) N ≦3 000.
6. (32 点) Xi , X j (1 ≦i < j ≦N),Yi , Y j (1 ≦i < j ≦N).
7. (31 点) 追加の制約はない.
IOI 熱の感染拡大– 2 / 6
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 1 – IOI Fever
入出力例
入力例1 出力例1
2 1
0 0
4 3
この入力例における家の位置関係は下図の通りとなる.
y
3 2
2
1
1
1 2 3 4 x
例えば,国民1 が「東」,国民2 が「南」の方向を選択したとする.
このとき,国民2 は国民1 と同じ座標に存在することはないので,国民2 は感染しない.したがって,時
刻10100 での感染者は国民1 のみであり,感染者数は1 人である.
国民1,国民2 がどのような方向を選択したとしても,感染者数が2 人以上とはならない.したがって,
求める感染者数の最大値は1 人であるため,1 を出力する.
この入力例は小課題1, 2, 3, 4, 5, 6, 7 の制約を満たす.
IOI 熱の感染拡大– 3 / 6
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 1 – IOI Fever
入力例2 出力例2
3 3
1 2
2 1
4 3
この入力例における家の位置関係は下図の通りとなる.
y
3 3
2 1
1 2
1 2 3 4 x
例えば,国民1 が「東」,国民2 が「北」,国民3 が「西」の方向を選択したとする.このとき,以下のよ
うに感染が拡大していく.
• 時刻0 において,国民1 のみがIOI 熱に感染している.
• 時刻1 において,国民1, 2, 3 の座標は順に(2, 2), (2, 2), (3, 3) となる.国民1 と2 が同じ座標に存在
し,国民1 はその時点で感染者であるため,非感染者である国民2 が新たに感染する.
• 時刻2 において,国民1, 2, 3 の座標は順に(3, 2), (2, 3), (2, 3) となる.国民2 と3 が同じ座標に存在
し,国民2 はその時点で感染者であるため,非感染者である国民3 が新たに感染する.
このとき,最終的な感染者数は3 人となる.これが最大値であるため,3 を出力する.
この入力例は小課題1, 2, 4, 5, 6, 7 の制約を満たす.
IOI 熱の感染拡大– 4 / 6
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 1 – IOI Fever
入力例3 出力例3
2 2
20 20
20 21
国民1 が「北」,国民2 が「南」の方向を選択した場合,以下のように感染が拡大していく.
• 時刻0 において,国民1 のみがIOI 熱に感染している.
• 時刻0.5 において,国民1, 2 両方が座標(20, 20.5) に存在する.国民1 はその時点で感染者であるた
め,非感染者である国民2 が新たに感染する.
このとき,最終的な感染者数は2 人となる.これが最大値であるため,2 を出力する.
この入力例は小課題5, 7 の制約を満たす.
入力例4 出力例4
15 9
5 6
2 9
12 0
4 11
3 12
6 5
0 8
9 10
11 13
8 7
13 2
1 1
7 14
10 4
14 3
この入力例は小課題2, 4, 5, 6, 7 の制約を満たす.
IOI 熱の感染拡大– 5 / 6
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 1 – IOI Fever
入力例5 出力例5
30 11
275810186 246609547
122805872 99671769
243507947 220373844
281305347 252104708
237805644 214671541
172469077 149334974
222589229 229887956
160653451 208404690
241378966 211098219
144302355 224755786
186392385 163258282
199129390 169928751
294937491 265736852
196096122 172962019
314342944 285142305
202720470 166337671
157037485 133903382
263858979 240724876
210720220 181519581
296402036 267201397
186021287 183036854
195081930 173976211
328293029 299092390
261195361 238061258
323595085 294394446
299933764 270733125
240976723 128081418
188501753 165367650
277832422 248631783
119896220 96762117
この入力例は小課題4, 5, 6, 7 の制約を満たす.
IOI 熱の感染拡大– 6 / 6