Magical Island 2

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem G: Magical Island 2

まだ魔法があたりまえのように存在した時代である.ある魔導士の一族は,魔力によって作られた正方形の形の島に住んでいた.

ある時,この島に危機が訪れた.帝国が大陸間弾道魔導ミサイルを開発し,この島を照準に合わせてきたのである.この世界の魔法は地属性,水属性,火属性,風属性などに分類でき,魔導ミサイルもその四つの属性のいずれかに属していた.島の四隅にはそれぞれ地の水晶,水の水晶,火の水晶,風の水晶が配置されていて,水晶に魔力を送り込むことで対応する属性の魔法攻撃を防ぐことがきでる.

魔導士達は帝国が開発した大陸間弾道魔導ミサイルによる攻撃をかろうじて退けることができた.しかし,帝国は新たに闇属性に属する大陸間弾道魔導ミサイルを開発し,再びこの島に攻撃を仕掛けてきた.闇属性に属する魔法はこの島に設置されている水晶で防ぐことはできない.そこで魔導士達は秘術としてこの島に伝えられる光属性の防御陣を用いてミサイルを防ぐ事にした.

この光属性の防御陣はある特定の形状をした魔法陣を大地に描くことにより発動する. 魔法陣は半径 R の円周を M 等分し K 個おきに直線で結んだ図形である.魔法陣は任意の大きさで描くことができるが魔法の発動には方角が重要なので,一つの角が真北を向くように描かなければならない.防御陣の効果が及ぶ範囲は描かれた魔法陣の内部(境界を含む)と一致する.またこの魔法の詠唱に必要なエネルギーは描いた魔法陣の半径 R と等しい.

図G-1は M = 4, K = 1 の場合である.灰色の部分が魔方陣の効果が及ぶ領域である. 図G-2は M = 6, K = 2 の場合である.図のように複数の図形が生じる場合は,それらの図形のいずれかに含まれていれば防御陣としての効果が及ぶ.


図G-1: M = 4 ,K = 1 の場合 小さい丸が集落を表す

図G-2: M = 6 ,K = 2 の場合

あなたの仕事は,集落の位置,および MK の値が与えられたときに,全ての集落をカバーするために必要となるエネルギーの最低量を求めるプログラムを書くことである.

Input

入力は複数のデータセットからなる. 各データセットは以下の形式で与えられる.

N M K
x1 y1
x2 y2
...
xN yN

最初の一行は 3 つの整数N, M, K からなる. N は集落の数を表す. M, K については問題文に記したとおりである. 2 ≤ N ≤ 50, 3 ≤ M ≤ 50, 1 ≤ K ≤ (M - 1) / 2を仮定してよい.

続く N 行は集落の位置を表す. 各行は二つの整数 xiyi からなる. xiyii 番目の集落のx座標とy座標を表す. -1000 ≤ xiyi ≤ 1000 を仮定して良い.y軸の正方向が北を指す.

入力の終わりはスペースで区切られた3個のゼロからなる.

Output

各データセットに対し,魔法陣の最小の半径 R を1行に出力せよ. 出力する値は10-6以下の誤差を含んでいても構わない.値は小数点以下何桁表示しても構わない.

Sample Input

4 4 1
1 0
0 1
-1 0
0 -1
5 6 2
1 1
4 4
2 -4
-4 2
1 5
0 0 0

Output for the Sample Input

1.000000000
6.797434948

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2010, 2010-06-27
http://acm-icpc.aitea.net/