Masala #0968
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.
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\}.\)
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.
| # | 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 |
Siz bergan javob va muallif javobidagi yo'l uzunliklari farqi \(10^{-6}\) dan katta bo'lganda javobingiz noto'g'ri deb hisoblanadi.
Telegram kanalimizga obuna bo'ling