Codeforces Round #803 (Div. 2)
05:18:27 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
C. Цэцэг услах
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Цэцгийн хүлэмж нь маш олон цэцгүүд болон 2 ширхэг усан оргилууртай.
Та усны даралтыг өөрөө тохируулж болох ба ингэснээр та харгалзан эхний болон 2-дахь усан оргилуураас ус цацрах зай болох $r_{1}(r_{1} ≥ 0)$ болон $r_{2}(r_{2} ≥ 0)$-уудын утгыг өөрөө тааруулах юм.Та заавал бүх цэцэг услагдсан байхаар $r_{1}$ болон $r_{2}$-ыг тааруулах бөгөөд түүнчлэн бүх цэцгийн хувьд эхний усан оргилуураас $r_{1}$-ээс хэтрэхгүй зайд байна эсвэл 2-дахь усан оргилуураас $r_{2}$-оос хэтрэхгүй зайд байх юм.Мөн зарим цэцэг 2 усан оргилуураар хоёулангаар нь услагдаж болно.
Та усалгаанд шаардагдах усны хэмжээг багасгах хэрэгтэй бөгөөд үүний тулд бүх цэцэг услагдсан байх ба $r_{1}^{2} + r_{2}^{2}$ нийлбэр боломжит хамгийн бага утгаа авч байхаар $r_{1}$ болон $r_{2}$-ыг тааруулах юм.Тэгвэл энэ нийлбэрийн хамгийн бага утгыг олно уу.
Оролт
Эхний мөрөнд цэцгийн тоо,эхний болон 2-дахь усан оргилуурын координатуудыг илэрхийлэх бүхэл тоонууд $n$, $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ ($1 ≤ n ≤ 2000$, $-10^{7} ≤ x_{1}, y_{1}, x_{2}, y_{2} ≤ 10^{7}$) өгөгдөнө.
Дараагийн $n$ мөрний $i$-дахь мөрөнд $i$-дахь цэцгийн координатууд болох бүхэл тоонууд $x_{i}$ болон $y_{i}$ ($-10^{7} ≤ x_{i}, y_{i} ≤ 10^{7}$) өгөгдөнө.
Мөн эдгээр оролтод өгөгдөх $n + 2$ ширхэг цэгүүд нь бүгд ялгаатай цэгүүд байна.
Гаралт
$r_{1}^{2} + r_{2}^{2}$-ын боломжит хамгийн бага утгыг хэвлэнэ.
Тэмдэглэл: тус бодлогын оновчтой хариулт нь үргэлж бүхэл тоо байна.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
2 -1 0 5 3 0 2 5 2
Гаралт
6
Оролт
4 0 0 5 0 9 4 8 3 -1 0 1 4
Гаралт
33
Тэмдэглэл
Эхний жишээнд $r_{1}^{2} = 5$, $r_{2}^{2} = 1$ байна:
2-дахь жишээнд $r_{1}^{2} = 1$, $r_{2}^{2} = 32$ байна: