A - 役人

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

あなたは、川と緑に囲まれた小さいながらも豊かな王国の役人です。
この国では敷地の境界線をきちんと決めていなかったため土地の所有権をめぐる争いが絶えませんでした。
新しい王からこの問題を解決するように指示されたあなたは敷地の境界線を決めることにしました。

あなたが担当している地域に大きめの木が300本あったのでこれを目印にすることにしました。
それぞれの敷地は3つの木を選んでできる三角形の形をしています。
王国の住人はプライバシーに気を使うので敷地の境界が少しも触れていないようにする必要があります。
すなわち、敷地の境界線を共有していたり、敷地の角を共有していてはいけません。
もちろん、敷地が重なることがあってはなりません。
この条件を満たしつつ敷地の数を最大化しましょう。

入力

入力は以下の形式で標準入力から与えられる。 
X1 Y1
X2 Y2
...
X300 Y300
  • i 番目の木の座標を表す整数 Xi Yi (1 ≦ i ≦ 300 , -1000 ≦ Xi,Yi ≦ 1000) が空白区切りで 300 行与えられる。
  • ただし、3本の木が一直線上に並ぶことはない。

出力

出力は以下の形式で標準出力から出力すること。 
N
p1,1 p1,2 p1,3
p2,1 p2,2 p2,3
...
pN,1 pN,2 pN,3
  • 1行目には境界を決めた敷地の数 N を出力すること。
  • 2行目からN+1行目にはそれぞれの敷地を決めるのに使った3本の木の番号を空白区切りで出力すること。ただし、木の番号とは入力で与えられる順番のことであり、1〜300である。
  • 各行の最後には改行を出力すること。

部分点

この問題の点数は決めた敷地の数 N によって計算されます。
各テストケースについて N / 100 が点数になります。
ただし出力が制約を満たさない場合、そのテストケースについての点数は 0 になります。
テストケースは100ケースあります。

入力例

-724 -666
849 411
820 769
-86 -961
972 530
-735 412
254 -106
-460 146
-221 -816
776 -979
549 -469
117 59
-442 587
199 -95
-664 -303
-376 340
-169 248
-53 496
332 -875
763 833
510 -758
-219 306
933 -192
860 467
75 -89
-697 346
912 -194
450 436
426 215
-737 285
479 -440
98 -759
-493 95
646 -126
-343 742
-573 45
-930 -511
-681 -439
538 -293
-698 198
-519 855
238 -48
-46 -815
70 -896
-15 464
-534 -921
-573 -448
922 -706
-434 -466
-171 989
205 538
168 -538
429 292
-871 -510
739 -829
-423 -384
498 43
-501 -589
894 -910
-757 -238
531 326
390 -82
763 -858
334 659
-972 409
-723 -182
395 -551
-485 580
-654 214
-515 -646
-541 -852
-305 -84
742 145
507 833
332 870
847 635
992 -329
3 -614
-654 390
-261 -590
868 882
834 -417
50 -149
-801 -341
-898 -887
-93 -427
850 -508
59 -109
-321 -627
724 876
360 621
-433 312
-190 -266
641 -914
581 -541
448 946
-230 605
-472 510
577 -559
-416 -253
594 53
-734 990
192 -744
-828 -148
-94 -402
-464 -779
132 -81
914 -952
-60 -976
-65 -556
-107 -677
-895 -163
-450 611
474 468
-722 888
-971 481
-15 -359
30 -879
813 -775
-441 -72
834 798
693 -308
762 460
809 12
71 709
375 -115
-528 52
341 529
248 414
914 -103
-223 -62
999 -300
641 743
835 892
477 78
825 -232
-636 -81
-696 -286
-677 721
-209 -797
-971 66
-610 264
812 773
-740 578
129 -177
-59 940
86 -613
-580 921
-820 -679
-812 238
315 -225
777 206
338 -549
-244 385
502 887
-344 487
997 -82
919 -963
-78 932
602 227
762 705
486 281
-105 -10
937 -571
116 152
838 140
-746 -984
783 417
-161 -685
-641 129
69 351
982 153
-780 5
405 184
-122 237
116 -147
643 626
-676 -763
264 644
-696 -944
823 923
500 -373
290 -386
-622 738
-137 -555
-604 -613
-873 732
170 905
-247 -118
124 657
389 292
-108 791
494 -758
-129 745
170 -568
212 120
-148 52
-302 -991
26 -237
-114 -361
485 43
-376 1000
668 -570
-99 -818
610 -74
-133 -457
-553 -178
-467 -465
-93 -270
-384 586
-321 -780
598 -890
261 724
-902 -152
645 994
-767 61
-693 70
-383 -211
990 632
404 -975
263 -853
-470 -654
621 965
-144 -595
-755 554
-917 -386
202 497
-712 260
-526 89
-464 -990
-352 -513
-116 754
708 356
-623 -642
860 -915
28 -205
-21 824
-539 -333
391 741
205 -77
524 -380
858 -483
965 -799
-744 -79
248 15
-962 -571
-938 243
-420 -484
-883 851
18 -700
211 660
694 122
877 390
188 -154
676 -33
259 957
378 -142
624 -860
-855 864
771 -969
601 29
-140 -241
154 384
933 619
-555 732
-368 -299
128 487
-318 220
-964 -175
-994 -573
910 36
497 88
-230 -535
963 683
-714 -150
-835 -151
569 506
-525 -339
896 570
802 497
508 908
-105 570
-625 -383
-786 517
309 118
643 644
649 111
-501 188
-762 317
-250 406
-367 344
-892 568
199 688
54 942
-855 -697
-141 -695
340 -137
-965 -54
442 -108
-729 90

出力例

10
81 294 215
89 166 169
158 43 172
3 259 41
293 76 29
84 214 249
284 287 178
270 149 1
171 125 68
299 273 257

出力例の場合、このケースのポイントは 10 / 100 = 0.10 になります。

B - 玉座の間

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

あなたは、両親から引き継いだ、川と緑に囲まれた小さいながらも豊かな王国の統治者です。
王位を引き継ぐにあたって玉座の間の改装を行うことにしました。
とても几帳面なあなたは家具が左右対称になっていないと気がすみません。
しかし、家具をあちこち移動させていると改装費がかさんでしまいます。
あなたは家具を左右対称になるように動かす時の、家具の移動距離の合計を最小化することにしました。

家具は2次元上の点として考えます。家具には種類がなく、区別しません。
左右対称な状態とは、y軸について反転させた時に同じ状態になることです。
例えば、(-1,0),(0,0),(1,0)に家具がある状態は、反転させると(-1,0),(0,0),(1,0)となり、同じ状態なので左右対称です。
しかし、(-1,0),(1,0),(1,0)に家具がある状態は、反転させると(-1,0),(-1,0),(1,0)となり、違う状態なので左右対称ではありません。
家具はどのような経路でも動かせて、家具同士が重なってもかまいません。

入力

入力は以下の形式で標準入力から与えられる。 
N
X1 Y1
X2 Y2
...
XN YN
  • 1行目には家具の数を表す整数 N が与えられる。
  • 2行目からN+1行目には家具の座標を表す整数 Xi Yi (1 ≦ i ≦ N , -1000 ≦ Xi,Yi ≦ 1000) が空白区切りで与えられる。
  • 与えられる家具の座標はすべて異なる。すなわち、i ≠ j ならば (Xi,Yi) ≠ (Xj,Yj) を満たす。

出力

左右対称にするのに必要な家具の移動距離の合計の最小値を出力すること。
小数点以下何桁でも出力してよく、絶対誤差・相対誤差の少なくとも片方が10-6以下であれば正答と見なされる。

部分点

この問題は(1)〜(4)の部分点に分かれていて、それぞれ以下の条件を満たします。

  • (1) 50点 : N = 1
  • (2) 50点 : 1 ≦ N ≦ 10
  • (3) 50点 : 1 ≦ N ≦ 20
  • (4) 50点 : 1 ≦ N ≦ 100

入力例 1

1
1 0

出力例 1

1.0000000

家具を(0,0)に移動させるのが最適であり、移動距離の合計は1となります。

入力例 2

3
-1 0
0 0
1 0

出力例 2

0.0000000

すでに左右対称なので家具を移動させる必要はありません。

入力例 3

2
2 2
-2 1

出力例 3

1.0000000

例えば、家具を(2,1.5),(-2,1.5)に移動させると移動距離の合計は1になります。

入力例 4

8
2 2
7 1
9 -4
-10 1
-6 -9
-6 10
8 8
2 -4

出力例 4

15.6593790
C - 泥棒

Time Limit: 5 sec / Memory Limit: 64 MB

問題文

あなたは、川と緑に囲まれた小さいながらも豊かな王国の泥棒です。
新しい王が治安向上のために監視所を設置し始めたので監視に引っかからないように気をつける必要があります。
監視所では他の監視所との間をまっすぐ結んだ線の上に誰がいるかを調べています。
あなたはこの線を横切ったり、線上の家に盗みに入ることはできません。
もちろん、監視所を通過することも出来ません
盗みに入る家と監視所の位置が与えられるので監視に引っかからずにアジトから盗みに入る家までたどり着けるか調べましょう。
ただし、盗みに入る段階でまだ設置されていない監視所について監視に引っかかることはありません。

入力

入力は以下の形式で標準入力から与えられる。 
N
S1 X1 Y1
S2 X2 Y2
...
SN XN YN
  • 1行目には盗みに入る家と監視所の数の合計を表す整数 N が与えられる。
  • 2行目からN+1行目には、盗みに入る家か監視所であるかを表す文字列 Si と、座標を表す整数 Xi Yi (1 ≦ i ≦ N , 1 ≦ Xi,Yi ≦ 108) が空白区切りで与えられる。
  • Si は TARGET もしくは MONITOR であり、それぞれ盗みに入る家と監視所を表している。
  • 盗みに入る家・監視所は全て違う位置にある。すなわち、 i ≠ j ならば (Xi,Yi) ≠ (Xj,Yj) を満たす。
  • 家に盗みに入る日時・監視所が設置される日時は入力で与えられる順の通りである。
    すなわち、ある家に盗みに入る時に既に設置されている監視所とはそれより前の入力で与えられた監視所のことである。
  • アジトは原点(0,0)にある。

出力

それぞれの盗みに入る家に対して入力の順に監視所に引っかからずに盗みに入れるかを判定し、監視に引っかからないなら SAFE 、引っかかるなら DANGER と出力すること。
各行の最後には改行を出力すること。

部分点

この問題は(1)〜(4)の部分点に分かれていて、それぞれ以下の条件を満たします。

  • (1) 50点 : 盗みに入る家は1箇所 監視所は3箇所以下
  • (2) 50点 : 盗みに入る家は100箇所以下 監視所は100箇所以下
  • (3) 50点 : 盗みに入る家は1000箇所以下 監視所は1000箇所以下
  • (4) 150点 : 盗みに入る家は100000箇所以下 監視所は100000箇所以下

入力例 1

4
MONITOR 1 1
MONITOR 5 1
MONITOR 1 5
TARGET 2 2

出力例 1

DANGER

どのように移動しても監視所をまっすぐ結んだ線の上を通らないと盗みに入ることはできません。

入力例 2

4
MONITOR 1 1
MONITOR 5 1
TARGET 2 2
MONITOR 1 5

出力例 2

SAFE

(1,5)に設置される３つ目の監視所が盗みに入るよりも後に設置されるので、監視に引っかからずに盗みに入ることができます。

入力例 3

7
MONITOR 2 1
MONITOR 4 1
MONITOR 6 1
TARGET 1 1
TARGET 3 1
TARGET 5 1
TARGET 7 1

出力例 3

SAFE
DANGER
DANGER
SAFE

監視所をまっすぐ結んだ線の上の家には盗みに入ることはできません。

入力例 4

16
TARGET 51120745 10211893
MONITOR 20328222 81595946
TARGET 24623254 3393748
MONITOR 96914389 5611093
MONITOR 26478507 21094604
MONITOR 38390485 52094021
MONITOR 54035108 52551113
MONITOR 32344389 92111226
MONITOR 42882326 49216313
TARGET 82009425 13194112
TARGET 36823977 72449795
TARGET 63951760 31282888
MONITOR 20099707 13753116
MONITOR 19673434 2381167
TARGET 135597 680580
TARGET 21578019 66062479

出力例 4

SAFE
SAFE
DANGER
DANGER
DANGER
SAFE
DANGER
D - 魔女

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

あなたは、川と緑に囲まれた小さいながらも豊かな王国の魔女です。
新しい王が王国を視察することを聞いたあなたは仲間と一緒に邪魔することにしました。
魔女は自分を中心とした円の内側に呪いをまき散らすことができます。
また、魔力が強い魔女は円の大きさをだんだん大きくすることが可能です。
王はこの円の中に入ると呪いを受けてしまうので避けながら移動しなければなりません。
王が出発地から目的地へ最短で移動するときにかかる時間を求めましょう。
ただし、王が呪いを受けることなく目的地に到着できないときは Impossible と出力してください。

入力

入力は以下の形式で標準入力から与えられる。 
Sx Sy Gx Gy V N
W1,x W1,y W1,r W1,v
W2,x W2,y W2,r W2,v
...
WN,x WN,y WN,r WN,v
  • 入力はすべて整数で与えられる。
  • 1行目には出発地の座標 Sx Sy 、目的地の座標 Gx Gy 、王が1分間に移動する距離 V 、魔女の人数 N が空白区切りで与えられる。
  • 2行目からN+1行目には、魔女の座標 Wi,x Wi,y 、王が出発する時点での呪いの半径 Wi,r 、呪いの半径が1分間で広がる距離 Wi,v が空白区切りで与えられる。
  • 王が出発してから t 分後の呪いの半径は Wi,r + Wi,v * t となる。例えば、 Wi,r = 1, Wi,v = 2 の場合、 0.5 分後に呪いの半径は 2 となる。
  • 呪いの半径は連続的に大きくなる。
  • 出発地・到着地は王が出発する時点で呪い受ける範囲内ではなく、境界上でもない。

出力

王が呪いを受けることなく出発地から目的地に辿り着けないときは Impossibleと出力すること。
辿り着ける場合は王が出発してから目的地に到着するのに最短で何分かかるか出力すること。
小数点以下何桁でも出力してよく、絶対誤差・相対誤差の少なくとも片方が10-6以下であれば正答と見なされる。
ただし、呪いの範囲の境界上では呪いを受けることはない。
また、王が出発する時点でのいずれかの魔女の呪いの半径が Wi,r - 10-3 から Wi,r + 10-3 の範囲で変化しても呪いを受けずに目的地に辿り着けるかどうかは変わらない。

制約

  • -1000 ≦ Sx, Sy, Gx, Gy, Wi,x Wi,y ≦ 1000
  • (Sx, Sy) ≠ (Gx, Gy)
  • 1 ≦ V ≦ 100
  • 1 ≦ N ≦ 10
  • 1 ≦ Wi,r ≦ 1000
  • 0 ≦ Wi,v ≦ 100

部分点

この問題は(1)〜(4)の部分点に分かれていて、上で与えられた条件の他に以下を満たします。

  • (1) 50点 : N = 1 かつ Wi,v = 0
  • (2) 100点 : Wi,v = 0
  • (3) 100点 : Wi,v = 0 または V < Wi,v
  • (4) 150点 : N = 1 かつ 0 < Wi,v < V

入力例 1

0 0 10 10 2 1
5 5 5 0

出力例 1

8.926990817

入力例 2

0 0 10 10 2 2
4 6 4 0
6 4 4 0

出力例 2

9.141592654

入力例 3

0 0 10 10 2 2
4 6 4 0
6 4 4 3

出力例 3

Impossible

入力例 4

22 53 98 32 4 1
69 40 2 1

出力例 4

21.425021992