Optimal Space Way
Bu 2180-ci ildir, insan irqi Yeri tərk etməyə və mədəniyyətini kosmosa yaymağa başlayıb. ACM (Kosmik Maşinizm Assosiasiyası) bu köçürmə prosesinə rəhbərlik edir və bu proses əsasən IBM (Planetlərarası Ballistik Maşınlar) tərəfindən maliyyələşdirilir. Minlərlə kosmik şəhər kosmosda tikilib və universal iş saatını (bütün kosmik şəhərlərdə günəşin eyni vaxtda doğub batması) saxlamaq üçün onlar eyni xəyali müstəvidə tikilib. Beləliklə, şəhərlərin yeri iki ölçülü Dekart koordinatları ilə ifadə edilə bilər.
Şəhərlər bir-birindən çox uzaqda yerləşir və bir şəhərdən digərinə getməyin yeganə yolu şatl raketlərindən istifadə etməkdir. Lakin əvvəlki təcrübədən ACM bilir ki, yollarla səyahət etmək raketlərlə səyahət etməkdən daha ucuzdur. Buna görə də bəzi yollar tikməyə qərar veriblər. Lakin hər bir şəhər cütü arasında yollar tikmək çox bahalıdır. Buna görə də onlar düz bir yol olacaq super kosmik yol (SSW) tikməyi planlaşdırırlar. Kimsə c_1 şəhərindən c_2 şəhərinə getməli olduqda, əvvəlcə c_1 şəhərindən SSW-ya ən yaxın nöqtəyə raketlə gedir və SSW boyunca c_2 şəhərinə ən yaxın nöqtəyə hərəkət edir. Sonra oradan c_2 şəhərinə başqa bir raketlə gedir. Yol boyunca hərəkət etmə xərci məsafə ilə mütənasibdir, lakin raketlərlə uçma xərci məsafənin kvadratı ilə mütənasibdir. Beləliklə, SSW-ni elə bir mövqedə tikməlisiniz ki, raketlərlə səyahətin illik təqvim üzrə ümumi xərci minimum olsun. Siz aşağıdakıları fərz edə bilərsiniz:
Şəhərlər aralarındakı məsafə ilə müqayisədə o qədər kiçikdir ki, iki ölçülü Dekart koordinat sistemində nöqtələr kimi qəbul edilə bilər.
SSW şəhərlər arasındakı məsafə ilə müqayisədə o qədər dardır ki, düz xətt kimi qəbul edilə bilər. Raketlərlə səyahətin ümumi xərci azaldıqda, SSW-nin uzunluğu hər iki istiqamətdə qeyri-müəyyən şəkildə artırıla bilər.
Sadəlik üçün hər bir şəhərdən gələn və gedən raketlərin ümumi sayının eyni olduğunu fərz edə bilərsiniz.
Bəzən bir şəhər bütün fəaliyyətlərin mərkəzi olan super şəhər kimi işarələnə bilər. Bu halda, həmin şəhərin gələn və gedən uçuşlarının ümumi sayı adi bir şəhərdən M dəfə çoxdur.
Bütün raketlərin düz xətt üzrə uçduğunu fərz edin.
Bütün şəhərlərin yerini nəzərə alaraq, raketlərlə səyahətin ümumi xərci minimum olan SSW üçün bir yer tapmalısınız. Və siz raket uçuşu başına minimum orta xərci istehsal etməlisiniz, fərz edərək ki, v vahid məsafə uçma xərci v^2-dir.
Giriş verilənləri
Giriş faylı 50-dən az test halı ehtiva edir. Hər bir test halının təsviri aşağıda verilmişdir:
Hər bir test halı iki tam ədəd N (0 < N ≤ 10000) və Q (0 < Q ≤ 100) ilə başlayır. Burada N kosmosda tikilmiş ümumi şəhər sayını, Q isə ümumi sorğu sayını göstərir. Növbəti N sətirin hər biri iki ondalık nömrə, x_i, y_i (0.0 ≤ x_i, y_i ≤ 1000.0) ehtiva edir ki, bu da i-ci şəhərin koordinatını göstərir. Şəhərlər giriş faylında göründükləri ardıcıllıqla 0-dan N-1-ə qədər nömrələnir. Növbəti Q sətirin hər biri iki tam ədəd S (0 ≤ S ≤ N-1) və M (1 < M ≤10000) ehtiva edir. Burada S super şəhərin id-sini göstərir və M onun super şəhərdə gələn və gedən uçuşlarının ümumi sayının adi bir şəhərdən M dəfə çox olduğunu göstərir.
İki sıfır ehtiva edən bir sətir girişi bitirir. Bu sətir işlənməməlidir.
Çıxış verilənləri
Hər bir test halı üçün Q+2 sətir çıxış istehsal edin. İlk sətir iş nömrəsini ardınca iki nöqtə ilə ehtiva edir. İkinci sətir optimal super kosmik yol üçün raket uçuşu başına minimum orta xərci göstərən ondalık nömrəni ehtiva edir (Bütün şəhərlərin adi olduğunu fərz edərək). Bu sətir ardınca hər bir sorğu üçün bir sətir gəlir. Bu sətir sorğunun ardıcıllığını və ondalık nömrəni ehtiva edir. Bu nömrə S-ci şəhərin super şəhər olduğunu və digər bütün şəhərlərin adi olduğunu fərz edərək optimal super kosmik yol üçün minimum orta xərci göstərir. Çıxışdakı bütün ondalık nömrələr ondalıkdan sonra beş rəqəm ehtiva etməlidir. Nümunə giriş üçün çıxışa baxın. Bütün ondalık çıxışlar üçün 10^{-5}-dən az olan mütləq səhvin nəzərə alınmayacağını fərz edə bilərsiniz.