E. Алёона ба гурвалжнууд

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

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

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

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

Танд хавтгай дээрх бүхэл тоон координатуудтай $n$ ширхэг цэг өгөгджээ. Түүнчлэн эдгээр $n$ ширхэг цэгүүдийн аль ч 3-аар нь үүсэх гурвалжнуудын талбай нь $S$-ээс хэтрэхгүй байхаар өгөгдөв.

Алёона бүхэл тоон координатуудтай гурвалжин байгуулахыг оролдож байгаа бөгөөд ингэхдээ уг гурвалжин нь бүх $n$ ширхэг цэгийг агуулах ба талбай нь $4S$-ээс хэтрэхгүй байх ёстой байв. Гэхдээ тодорхой шалтгааны улмаас тэрээр үүнийг амжилттай байгуулж чадахгүй байв. Алёона-д туслан ийм байх гурвалжин байгуулж өгнө үү. Хариултын гурвалжны оройнууд нь заавал өгөгдсөн $n$ ширхэг цэгүүд дээр байх ёсгүйг анхаарна уу.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $S$ ($3 ≤ n ≤ 5000$, $1 ≤ S ≤ 10^{18}$) өгөгдөх ба эдгээр нь харгалзан өгөгдсөн цэгийн тоо болон өгөгдсөн $n$ ширхэг цэгүүдийн аль ч 3-н цэгээс үүсэх гурвалжнуудын талбайн дээд хязгаарыг илэрхийлнэ.

Дараагийн $n$ мөрөнд өгөгдсөн цэгүүдийг дүрсэлнэ: эдгээрийн $i$-р мөр нь 2 бүхэл тоо $x_{i}$ болон $y_{i}$ $( - 10^{8} ≤ x_{i}, y_{i} ≤ 10^{8})$-аас тогтох ба эдгээр нь $i$-р цэгийн координатуудыг илэрхийлнэ.

Түүнчлэн дор хаяж нэг ширхэг цэгүүдийн гурвал нэг ижил шулуун дээр оршоогүй байна.

Гаралт

3-н цэгийн координатуудыг хэвлэх ба эдгээр нь бүх $n$ ширхэг цэгүүдийг агуулах ба талбай нь $4S$-ээс хэтрээгүй байх гурвалжны оройнуудыг илэрхийлэх юм.

Тус гурвалжны орой болгоны координатууд нь тусдаа мөрөнд хэвлэгдэх ёстой ба координатын хос болгон нь хоорондоо нэг хоосон зайгаар тусгаарлагдсан байна. Мөн координатууд нь абсолют утга нь $10^{9}$-өөс хэтрээгүй байх бүхэл тоонууд байх ёстой.

Дор хаяж нэг ширхэг хариултын гурвалжин оршин байх бөгөөд хэрэв нэгээс олон хариулт байвал та тэдгээрийн алийг нь ч хэвлэсэн болно.

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

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

Оролт
4 1
0 0
1 0
0 1
1 1
Гаралт
-1 0
2 0
0 2

Тэмдэглэл

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