Hide

Problem E
イースターエッグ

Languages en ja
/problems/eastereggs/file/statement/ja/img-0001.jpg
Picture by wackystuff via Flickr.

まもなくイースターなので、イースターバニーは子供たちのためにチョコレートエッグ狩りを行うことを決めた。

彼は青いミルクチョコレートと赤いダークチョコレートの2種類の卵を隠す。フィールドには、卵を隠すことができるようなレッドベリーとブルーベリーが生えている。 赤い卵はレッドベリーに、青い卵はブルーベリーに隠す必要がある。 地方自治体は、ちょうど $N$ 個の卵を隠すという条件でこのイベントを許可した。 自治体は歯科の治療計画に予算を立てていないため、イースターバニーは各色の卵を何個ずつ隠すかについて、自分で決めることにした。 伝統的に、赤い卵と青い卵の両方を最初に見つけた子供には賞が与えられる。 狩りを挑戦的にするために、イースターバニーは赤い卵と青い卵との最小距離を最大化しようと考えている。 フェアにするため、ある植物に複数の卵を隠すことはない。あなたのタスクは、彼の目的に沿うプログラムを作ることだ。

入力

入力は以下の内容を含む。

  • 先頭行は3つの整数 $N, B, R$ で、隠す卵の数 $N$$N \leq 250$、ブルーベリーの数 $B$$B < N$ 、レッドベリーの数 $R$$R < N$

  • その後 $B$ 行は2つの整数で、$-10^4 \leq x,y \leq 10^4$$(x,y)$ がブルーベリーの座標を表す。

  • その後 $R$ 行は2つの整数で、$-10^4 \leq x,y \leq 10^4$$(x,y)$ がレッドベリーの座標を表す。

$B+R$ 個の植物は異なる位置にあることが保証される。加えて、$N \leq B+R$ であることも保証される。

出力

単一の浮動小数点数 $D$ を出力する。これは、赤い卵と青い卵の最小距離の最大値を表す。 $D$ は小数点以下6桁以上の精度、すなわち、最低6桁の小数を出力する必要がある。

\includegraphics[width=.3\textwidth ]{./sample-testcase2.pdf}
図 1: Illustration of the second example input. The eggs are hidden in the four filled bushes.
サンプル入力 1 サンプル出力 1
3 2 2
0 0
1 0
2 0
3 0
2.000000000000000
サンプル入力 2 サンプル出力 2
4 3 3
0 0
1 2
-1 2
0 1
-1 -1
1 -1
3.000000000000000