E. Сайдад зориулсан гэрлийн чийдэн

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

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

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

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

Боловсролын сайд ирж байна! Ерөнхийдөө хэн ч ийм хүндтэй зочны өмнө хангалтгүй харагдахыг хүсэхгүй. Гэхдээ ирэхээс нь хоёр цагийн өмнө нэг ангийн гэрлийн чийдэн нь хангалттай энерги авахгүй байгаагаас болж буруу ажиллаж эхэлсэн. Шийдлийг түргэн олсон ба бидний хийх ёстой зүйл нь чийдэнгийн байршлыг сольж хамгийн их хэмжээний энергитэй болгох юм.

Чийдэнгийн чадал нь байдгийг хүн бүр мэдэх ба энд $C$ нь тогтмол утга ба $r_{i}$ нь чийдэнгээс $i$-р үүсгүүр хүртэлх Эвкледийн зай юм. Иймээс бидний ажил бол -г хамгийн бага болгох юм. Мэдээж бид бүх үүсгүүрийн байрлалуудыг мэднэ.

Чийдэн ангийн таазанд байрлах ёстой. Ангийн тааз нь гүдгэр $m$ өнцөгт байна (анги нь өөрөө гүдгэр $m$ өнцөгт шал бүхий олон талт хэлбэртэй байна). Чийдэнгийн хамгийн тохиромжтой байрлалыг олоход туслана уу. Бүх үүсгүүр нь ангийн таазны хавтанд байрлана. Ангийн таазны хавтан нь координатын системтэй.

Оролт

Эхний мөрөнд бүхэл тоо $n$ $(2 ≤ n ≤ 10^{5})$ байх буюу үүсгүүрүүдийн тоо. Дараагийн $n$ мөр бүрт хос бүхэл тоо $x_{i}$, $y_{i}$ байх буюу ангийн таазны хавтан дээрх $i$-р үүсгүүрийн координатууд юм. Ямар ч хоёр үүсгүүр ижил байрлалд байрлахгүй.

Дараагийн мөрөнд бүхэл тоо $m$ $(3 ≤ m ≤ 10^{5})$ байх буюу ангийн таазыг тодорхойлох гүдгэр олон өнцөгтийн оройнуудын тоо байна. Дараагийн $m$ мөр бүрт хос бүхэл тоо $p_{i}, q_{i}$ байх буюу цагийн зүүний дарааллаар олон өнцөгтийн $i$-р цэгийн координатууд байна.

Бүх координатуудын үнэмлэхүй утга нь $10^{6}$-с хэтрэхгүй байна.

Гаралт

Үүсгүүрүүдийн байрлалаас гэрлийн чийдэнгийн хамгийн тохиромжтой байрлал хүртэлх зайн квадратуудын нийлбэрийн хамгийн бага утгыг илэрхийлэх нэг бодит тоог хэвлэ. Хариултын үнэмлэхүй эсвэл харьцангуй алдаа нь $10^{ - 4}$-с ихгүй тохиолдолд хариулт хүчинтэй.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4
3 2
3 4
5 4
5 2
4
3 3
4 4
5 3
4 2
Гаралт
8.00000000

Тэмдэглэл

Олон өнцөгтийн ямар ч гурван орой нь нэг шулуунд оршихгүй байвал бид үүнийг гүдгэр олон өнцөгт гэнэ.

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