E. Бослогын гэрч

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

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

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

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

Рамакана хөл бөмбөгийн цэнгэлдэхэд бослого болж байна! Ширүүн хөгжөөн дэмжигчид талбайд нэвтэрсэн ба цагдаа нар тэднийг хүнд нөхцөл байдлаас хайна. Талбай нь координатын системд (0,0) ба ($10^{5}$, $10^{5}$) оройтой диагональ бүхий квадрат хэлбэрээр дүрслэгдэж болно. Энэ квадратын талууд нь ч мөн талбайн дотор тал болох ба бусад бүх зүйл талбайн гадна тал болно.

Эхэндээ талбай дээр $N$ хөгжөөн дэмжигч байна. Хөгжөөн дэмжигч бүрийн хувьд бидэнд түүний хурд $v_{i}$ бүхэл тоо болон түүний бүхэл тоон координат ($x_{i}$, $y_{i}$) өгөгдөнө. Энэ координаттай хөгжөөн дэмжигч хөдлөж болох ба нэг секундын дараа тэр дурын ($x_{i} + p$, $y_{i} + q$) цэг дээр байж болох ба энд $0 ≤ |p| + |q| ≤ v_{i}$ байна. $p$ болон $q$ нь хоёулаа бүхэл тоонууд.

Талбайг илэрхийлэх квадратаас гадуур буй цэгүүдийг хасах ба бусад бүх цэгүүд нь тодорхой нэг хөгжөөн дэмжигчийн нэг секундын дараах байрлал байх тэнцүү магадлалтай.

Шинэ тангарагаа өргөсөн цагдаагийн офицер Андрей бослогын зургийг дээрээс нь авах нисдэг дрон нисгэсэн. Дроны камер дараах байдалтай ажиллана:

  1. Энэ нь нэг секундын дараа хөгжөөн дэмжигч харагдах магадлалтай байх бүхэл тоон координаттай гурван цэг сонгоно. Эдгээр цэгүүд нь нэг шулууны дагуу байрлахгүй хэрвээ ингэж байрлавал камер ажиллахгүй.
  2. Камер эдгээр цэгүүд дээр фокуслах ба эдгээр гурван цэгийг дайрсан тойрог үүсгэнэ. Нэг секундын дараа зураг авна (анхны төлвөөс нэг секундын дараа).
  3. Тойрог дээр байгаа эсвэл тойргийн дотор талд байгаа бүх зүйлс зурган (цэгүүд дээр фокусласнаас нэг секудын дараа) дээр бууна.

Таны зорилго бол зурган дээр харагдах хөгжөөн дэмжигчдийн тоо хамгийн их байхаар энэ гурван цэгийг сонгох юм. Хэрвээ хэд хэдэн ийм сонголтууд байвал хамгийн том радиустай тойрог үүсгэх цэгүүдийг сонго. Гэсэн ч тохирох олон сонголт байгаад байвал алийг нь ч сонгож болно. Хэрвээ таны хариулт дээрх нөхцөлүүдийг хангаж байвал мөн таны буцаасан тойргийн радиус хамгийн тохиромжтой тойргийнхоос 0.01-р бага байвал таны хариу зөвд тооцогдоно.

Ямар ч тестийн хамгийн тохиромжтой радиус $10^{10}$-с хэтрэхгүй.

Оролт

Эхний мөрөнд талбай дээрх хөгжөөн дэмжигчдийн тоо $N$ байна. Дараагийн $N$ мөр бүрт гурван бүхэл тоо $x_{i}$ ,$y_{i}$, $v_{i}$ байна. Эдгээр нь харгалзан $i$-р хөгжөөн дэмжигчийн бодлогод авч үзэж буй нэг секундын интервалын эхэнд байх $x$ координат, $y$ координат болон хурд нь байна.

  • $3 ≤ N ≤ 10^{5}$
  • $0 ≤ x_{i}, y_{i} ≤ 10^{5}$
  • $0 ≤ v_{i} ≤ 1000$
  • Бүх тоонууд бүхэл тоо байна.

Гаралт

Та камерийн сонгох ёстой гурван цэгийг хэвлэх ёстой. Эдгээрийг гурван мөрөнд хэвлэх ба мөр бүрт цэгийн $x$ координат болон $y$ координатыг зайгаар тусгаарлан хэвлэнэ үү. Цэгүүдийг дурын дарааллаар хэвлэж болно.

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

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

Оролт
3
1 1 1
1 1 1
1 2 1
Гаралт
2 2
2 1
1 0
Сэтгэгдлүүдийг ачааллаж байна...