Masala #0968

Xotira 256 MB Vaqt 4000 ms Qiyinchiligi 53 %

#Matematika

#Graflar nazariyasi

4.0 (Baholar 4)

Shimoliy city

Quruvchi elflar va nihoyat Shimoliy citydagi barcha binolarni qurib bitkazishdi, endigi vazifa esa bu binolarni yo'llar orqali bog'lab chiqish. Qiyin tarafi esa yo'llarni Yangi yil bayramigacha bitkazish kerak, chunki Shimoliy qutbda asosiy bayramlarni yangi Shimoliy cityda o'tkazish rejalashtirilgan. Yo'llarni iloji boricha tez bitirish uchun esa hamma binolarni birlashtiruvchi eng qisqa yo'lni topish kerak.

Kiruvchi ma'lumotlar:

Sizga $N$ natural soni va keyingi $N$ ta qatorda $X_i$ , $Y_i$ sonlari beriladi. $X_i$ , $Y_i$ bu i-binoning joylashgan koordinatalari. Binolar 1 dan N gacha raqamlangan.
$1\leq N \leq 1000;$ $-10^9 \leq X_i, Y_i \leq 10^9, \space i=\{1...N\}.$

Chiquvchi ma'lumotlar:

Quruvchi elflarga eng qisqa yo'l uchun qaysi binolar o'rtasida yo'llar qurish kerakligini yozib bering. O'rtasida yo'l qurilishi kerak bo'lgan bino juftliklari sonini va keyingi qatorlarda juftliklarni probel bilan ajratgan holda alohida qatorlarda chop eting.
Agar bir necha xil javob mavjud bo'lsa, istalganini chop eting.

Misollar

#	input.txt	output.txt
1	5 0 0 0 4 4 0 2 2 4 4	4 1 4 2 4 3 4 4 5
2	9 -10 5 -3 6 8 6 -4 1 4 2 0 0 -5 -8 2 -8 7 -9	8 4 6 5 6 2 4 8 9 3 5 7 8 1 2 6 8

Izoh:

Siz bergan javob va muallif javobidagi yo'l uzunliklari farqi $10^{-6}$ dan katta bo'lganda javobingiz noto'g'ri deb hisoblanadi.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin