Category

Similar Problems

0666. Minionlar va olov

Time limit : 1000 ms
Memory limit : 64 mb

Minionlar daryo bo’yiga dam olishga borishdi. Baliq pishirishyotip, gugurt bilan extiyotsiz muomalada bo’lishi oqibatida yong’in kelib chiqdi. Endi olov tarqalib ketmasdan oldin uni zudlik bilan o’chirish kerak.  Baxtga qarshi ularning yong’in o’chiruvchi apparati boshqa yerda qolgan va u bo’m-bo’sh. Olov paydo bo’lgan nuqtdan apparatga borib, uni daryodan suvga to’ldirib keyin uni yana olov chiqqan nuqtaga olib kelish kerak. Bu ishni esa tezlik bilan bajarish kerak. Shunin uchun bunday harakatdagi eng qisqa yo’l bilan harakatlanish kerak. Ularga bu eng qisqa yo’lni topishda yordam bering.

Kiruvchi ma’lumotlar

Birinchi qatorda daryoga to’g’ri chizig’iga tegishli bo’lgan ikki nuqtaning koordinatalari x1, y1 va x2, y2 sonlari beriladi.Ikkinchi qatorda  olov paydo bo’lgan nuqtaning koordinatalari x3, y3 va o’t o’chiruvchi apparat turgan nuqta koordinatalari x4, y4 sonlari beriladi.  Barcha koordinatalar butun va modul jihatdan 106 dan oshmaydi. Barcha nuqtalar har xil va (x3, y3) va (x4, y4) nuqtalari daryoga tegishli emas. 

Chiquvchi ma’lumotlar

Bitta sonni – eng qisqa yo’l uzunligini 10-6 aniqlikda chiqaring.

Misollar

Kiruvchi ma’lumotlar

Chiquvchi ma’lumotlar

1

1 -2 5 1

2 1 5 -1

7.211103

2

0 0 1 1

1 0 2 1

3.414214

 

Tayyorladi: Azat Yusupov
Online contest#8