Codeforces Round #716 (Div. 2)
04:03:18 |
Codeforces Round #717 (Div. 2)
2 өдрийн дараа |
Codeforces Round #718 (Div. 1)
4 өдрийн дараа |
Codeforces Round #718 (Div. 2)
4 өдрийн дараа |
Codeforces Global Round 14
13 өдрийн дараа |
G. Найрамдаж нутаг дэвсгэрээ хуваасан нь
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Фермер Жон МММ(Mischievous Mess Makers) нар эцэст нь найрамдахаар зөвшөөрчээ. Тэд орон даяар тархсан $n$ ширхэг зурвасаас хоёрыг нь дайрсан шулуун татаж Бовинийн газар нутгийг хуваахаар болжээ.. Зурвасууд $(x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n})$ цэгүүдэд байрлана.
Оптимал байдлаар хуваахын тулд тэд Бовинийн газрын зургийг координатын хавтгайд дүрсэлжээ. Фермер Жон болон МММ нар харгалзан $P = (a, 0)$, $Q = ( - a, 0)$ цэгүүдэд суурьшиж буй. Урт удаан хугацаанд үргэлжлэх найрамдал хүсч байгаа учир Бэсси, фермер Жон нар шулууны дурын цэгээс $P$, $Q$ цэгүүд хүртэлх зайн ялгаврын максимум утгыг хамгийн бага байлгахыг зорьж буй.
Илүү тодорхой хэлбэл, ![] (http://codeforces.com/predownloaded/86/84/8684977e56e9f2b9817d0c41d8143796eef18e29.png) шулуун дээрх дурын $X$ цэгийн хувьд $|PX - QX| \le d$ байх хамгийн бага $d$ бодит тоог шулууны хувьд $P$, $Q$ цэгүүдэд харгалзах ялгавар гэж нэрлэе. (Ийм $d$ орших ба цор ганц байна.) Тэд
шулууны $P$ and $Q$ цэгүүдэд харгалзах ялгавар хамгийн бага байх хоёр ялгаатай $(x_{i}, y_{i})$ and $(x_{j}, y_{j})$ зурвасыг дайрах
шулууныг олохыг эрмэлзэж байгаа юм.
Оролт
Эхний мөрөнд $n$, $a$ бүхэл тоонууд өгөгдөнө. ($2 ≤ n ≤ 100 000$, $1 ≤ a ≤ 10 000$)Харгалзан цэгүүдийн тоо болон суурин байршлыг илтгэнэ.
Удаах $n$ мөрөнд зурвасуудын байршлыг илтгэх бүхэл тоон хосууд $(x_{i}, y_{i})$ ($|x_{i}|, |y_{i}| \le 10 000$) өгөгдөнө. Цэгүүд өөр хоорондоо болон $P$, $Q$ цэгүүдээс ялгаатай байна..
Гаралт
Оптимал байдлаар хуваах шулууны ялгаврыг илтгэх нэг бодит тоог хэвлэнэ үү. Зөрүү нь $10^{ - 6}$ дотор байвал хариуг зөвд тооцно.
Хэрэв таны хариу $a$, зохиогчийн хариу $b$ байвал дараах нөхцөлд л шалгах програм таны хариуг зөвд тооцно:.
Орчуулсан: Төрбат
Жишээ тэстүүд
Оролт
2 5 1 0 2 1
Гаралт
7.2111025509
Оролт
3 6 0 1 2 5 0 -3
Гаралт
0.0000000000
Тэмдэглэл
Эхний жишээний хувьд ганц л боломжит шулуун байгаа нь $y = x - 1$. $|PX - QX|$ зай хамгийн утгаа авах $X$ цэг $(13, 12)$ болохыг харж болно.
буюу
.
Хоёр дах жишээнд $(0, 1)$, $(0, - 3)$ цэгүүдийг авбал шулуун $x = 0$ болно. Яагаад гэвэл энэ шулууны хувьд $PX = QX$ байх тул ялгавар $0$ юм.