E. Хөндлөн нийлбэр

хугацааны хязгаарлалт 7 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Женос-д Картесианы хавтгай дээр ялгаатай $n$ ширхэг шулуун өгөгджээ. -аар эдгээр цэгүүдийн огтлолцлын цэгүүдийн бүртгэлийг тэмдэглэе.Хэрэв нэг цэг нь олон тооны хос шулууны огтлолцлын цэг байвал уг бүртгэлд олон удаа орсон байж болно.Мөн уг бүртгэлийн дараалал нь ямар байх нь хамаагүй.

Өгөгдсөн асуултын $(p, q)$ цэгийн хувьд нь -ийн бүх цэгүүдээс асуултын цэг хүртэлх зайнуудын тохирох бүртгэлийг тэмдэглэв.Энд байгаа зайнуудыг эвклидийн зайг ашиглан олно.Сэргээж хэлэх үүднээс,$(x_{1}, y_{1})$ болон $(x_{2}, y_{2})$ 2 цэгийн эвклидийн зай нь байна.

Женос-д $(p, q)$ цэг болон эерэг бүхэл тоо $m$ өгөгдөнө.Түүнд -ын хамгийн бага $m$ элементийн нийлбэрийг олохыг даалгажээ.-ын давтагдсан элементүүдийг тусдаа элементүүд гэж үзнэ.Женос Div1 E-ын бодлогуудаас айдаг тул таны тусламжийг хүсжээ.

Оролт

Эхний мөрөнд шулуунуудын тоог илэрхийлэх ганц бүхэл тоо $n$ ($2 ≤ n ≤ 50 000$) өгөгдөнө.

2-дахь мөрөнд асуултын цэгийн кодлогдсон координатууд болон дээрх өгөгдлийн $m$ бүхэл тоог илэрхийлэх 3 бүхэл тоо $x$, $y$ болон $m$ ($|x|, |y| ≤ 1 000 000$, ) өгөгдөнө.Асуултын цэг $(p, q)$ нь хэлбэртэй өгөгдөнө.Өөрөөр хэлбэл,$x$ болон $y$-ыг $1000$-д хувааж байж жинхэнэ асуултын цэгийг олно.-аар бүртгэлийн уртыг тэмдэглэх ба байна.

Дараагийн $n$ мөрийн мөр болгонд хэлбэрээр өгөгдөх шулууны параметрүүд болох 2 бүхэл тоо $a_{i}$ болон $b_{i}$ ($|a_{i}|, |b_{i}| ≤ 1 000 000$) өгөгдөнө.

Аль ч 2 шулуун нь ижил байхгүй ба өөрөөр хэлбэл $(a_{i}, b_{i}) ≠ (a_{j}, b_{j})$ if $i ≠ j$ байх юм.

Гаралт

-ын хамгийн бага $m$ элементийн нийлбэр болох ганц бодит тоог хэвлэнэ.Таны хариулт хэрэв үнэмлэхүй болох харьцангуй алдаа нь $10^{ - 6}$-аас хэтрэхгүй бол зөвөөр тооцогдоно.

Тодруулах үүднээс, таны хариултыг $a$ шүүлтийн хариултыг $b$ гэж тэмдэглэе.Тэгвэл шалгагч программ нь хэрэв байвал таны хариултыг зөвөөр тооцох юм.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
4
1000 1000 3
1000 0
-1000 0
0 5000
0 -5000
Гаралт
14.282170363
Оролт
2
-1000000 -1000000 1
1000000 -1000000
999999 1000000
Гаралт
2000001000.999999500
Оролт
3
-1000 1000 3
1000 0
-1000 2000
2000 -1000
Гаралт
6.000000000
Оролт
5
-303667 189976 10
-638 116487
-581 44337
1231 -756844
1427 -44097
8271 -838417
Гаралт
12953.274911829

Тэмдэглэл

Эхний жишээнд, хамгийн ойр 3 цэгүүд нь болон зайтай байна.

2-дахь жишээнд, $y = 1000x - 1000$ болон гэсэн 2 шулуун нь $(2000000, 1999999000)$ цэг дээр огтлолцоно. Энэ цэг нь $( - 1000,  - 1000)$ цэгээс зайтай байх юм.

3-дахь жишээнд, 3-н шулуун нь бүгд $(1, 1)$ цэг дээр огтлолцоно.Энэ цэг нь 3-н хос шулууны огтлолцол учраас энэ огтлолцлын цэг нь дотор 3 байх юм.Огтлолцлын цэг болон асуултын цэгийн хоорондох зай $2$ учраас хариулт нь үүнийг 3-аар үржүүлсэн буюу $6$ байх юм.

Сэтгэгдлүүдийг ачааллаж байна...