D. Гинжин урвалууд

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

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

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

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

Тантай бизнесийн дотно харилцаатай байдаг Берландын судлаачдын бүлгэм энх тайвны цөмийн энергийн бүсэд судалгаа хийж байв. Тодруулбал тэд 4-н ширхэг нанобот (бичил робот)-ын бүлгэм олсон бөгөөд эдгээрийг нэгэн ялтасны гадаргуу дээр байрлуулсан байв. Мөн эдгээр наноботууд нь тодорхой нөхцөлүүдийг хангасан тохиолдолд маш хүчтэй гинжин урвал явуулж чаддаг байв.

Тодорхой болгох үүднээс, судлаачид хавтгай ялтас дээр тэгш өнцөгтөн Декартын координатын системийг танилцуулсан ба наноботууд нь анх байрлаж байх бүхэл тоон координаттай ялгаатай 4-н цэгийг сонгов. Түүнчлэн нанобот болгон нь координатын тэнхлэгүүдтэй параллель байх 4-н чиглэлийн (дээш, доош, зүүн эсвэл баруун) нэг чиглэлээр нь хөдөлж болдог байх юм. Үүний дараа нанобот болгон нь өөрийн чиглэлийн дагуу бүхэл тоон зайгаар шилжинэ (ялгаатай нанобот бүрийн хувьд шилжих зай нь ялгаатай байж болно). Хэрэв наноботууд нь талууд нь координатын тэнхлэгүүдтэй параллель бөгөөд эерэг талбай бүхий квадратын булангуудад байрлаж байвал уг гинжин урвал нь явагдаж эхлэх юм. Түүнчлэн уг квадратын булан болгон нь заавал нэг нанобот агуулах ёстой. Хэрэв наноботуудын хөдөлсөн хугацаа нь бага байвал уг гинжин урвал нь хүчтэй болох юм. Өөрөөр хэлбэл бид наноботуудыг нэгж хурдтай хөдөлнө гэж үзэх бөгөөд наноботуудын туулсан хамгийн урт зам нь аль болох бага байх тусам уг гинжин урвал нь илүү их хүчтэй явагдах юм.

Судлаачид хэсэг ялтаснуудыг бэлдсэн бөгөөд ялтас болгоны хувьд нанобот бүрийн анхны байрлалыг сонгосон байв. Одоо тэд танаас хөдөлж дууссаны дараа наноботуудын туулсан хамгийн урт зам нь аль болох бага байхаар нанобот болгоны хувьд хөдлөх чиглэлийг зааж өгөхийг хүсжээ.

Оролт

Эхний мөрөнд ялтасны тоо болох бүхэл тоо $t$ ($1 ≤ t ≤ 50$) өгөгдөнө.

Эдгээр ялтаснуудын $t$ ширхэг тайлбар нь дараах байдалтай байна. Ялтас болгоны тайлбар нь 4-н ширхэг мөрөөс тогтоно. Мөр болгон нь хос бүхэл тоонууд $x_{i}, y_{i}$ ($ - 10^{8} ≤ x_{i}, y_{i} ≤ 10^{8}$)-уудаас тогтох ба эдгээр нь зэргэлдээх наноботын координатуудыг илэрхийлнэ. Бүх наноботууд нь ялгаатай байрлал дээр байрласан байна.

Уг бодлого нь нэг тест дотроо хэд хэдэн дэд тест агуулж болохыг анхаарна уу. Иймд та бусад хүмүүсийн зөвхөн нэг ялтастай тесттэй үеийн бодолтуудыг ашиглаж болно. Өөрөөр хэлбэл ашиглаж болох тестүүдийн $t$ параметрийн утга нь $1$-тэй тэнцүү байх юм.

Гаралт

Бүх ялтаснуудын хувьд хариултуудыг тусдаа хэвлэнэ үү. Эхлээд дан мөрөнд нэг бүхэл тоо хэвлэнэ. Хэрэв судлаачид санамсаргүй алдаа гарган наноботууд бодлогын нөхцөл доторх квадратыг үүсгэж чадахгүй бол $-1$ гэж хэвлэнэ үү. Бусад тохиолдолд наноботуудын туулсан хамгийн урт замын боломжит хамгийн бага утгыг хэвлэнэ үү.

Хэрэв хариулт оршин байвал дараагийн 4-н мөрийн мөр болгонд 2 бүхэл тоо хэвлэх ба эдгээр нь хөдөлж дууссаны дараах наноботуудын байрлалыг илэрхийлнэ. Наноботуудын байрлалыг оролтод өгөгдсөн дарааллаар нь хэвлэнэ үү.

Хэрэв олон тооны хариулт байвал та тэдгээрийн алийг нь ч хэвлэсэн болно.

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

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

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