E. Хотыг аварна уу!

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

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

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

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

Аалам- Аара (Дэлхийн гэрэл гэгээ гэсэн утгатай) гэх тосгонд өмнө нь ямар ч гэмт хэрэг, ямар ч гэмт хэрэгтнүүд байдаггүй байсан ч цаг хугацаа өнгөрөхийн хэрээр нэгэн цагт үнэнч шударга байсан хүмүүсийн сэтгэлд нүгэл гэдэг зүйл бий болж эхэлжээ. Уг асуудлыг шийдэх арга хайсны үр дүнд хэсэг хөгшид гэмт хэрэгт холбогдсон хүн амын хэсгийг гэмт хэрэгт холбогдоогүй хүн амаас хол байлгаснаар гэмт хэргийг зогсоож болохыг олж мэджээ. Иймд тэд гэмт хэрэгт холбогдсон хүн амыг байлгадаг нэгэн хуаран байгуулахаар оролдож байгаа юм. Түүнчлэн гэмт хэрэгтнүүд уг хуарангаас оргохгүй гэдэгт итгэлтэй байхын тулд харуулын цамхаг барих хэрэгтэй бөгөөд ингэснээр харуулууд нь тэдгээрийг хянаж байх юм.

Аалам-Аара-ын хүмүүс нь баян биш учраас тэд өөр нэгэн баян тосгоны худалдаачнаас газар худалдан авахаар тохирсон ба уг газарт тухайн хашааны дагуу харуулын цамхаг барьж болох цөөн хэдэн цэг агуулсан $AB$ хашаа аль хэдийн баригдсан байв. Таны даалгавар бол тэдэнд туслан тухайн хашаан дээрх цамхаг барьж болох цэгийн тоог олох бөгөөд тухайн цэг дээр цамхаг барьснаар бүх гэмт хэрэгтнүүдийг хянаж болдог байх ёстой юм. Түүнчлэн зөвхөн ганцхан харуулын цамхаг баригдаж болно. Хэрэв харуулын цамхгаас гэмт хэрэгтэн хүртэлх үзэгдэх орчны хэрчим (өөрөөр хэлбэл цамхаг болон гэмт хэрэгтнийг холбосон хэрчим) нь худалдан авсан газар нутгийн ирмэгийг хөндлөн дайрч гараагүй бол уг гэмт хэрэгтнийг харуулын цамхгаас хянаж байна гэж үзнэ. Өөрөөр хэлбэл зураг 1-т дүрсэлснээр $X$, $Y$, $C$ болон $A$ гэсэн цэгүүд $B$ цэгээс хянаж болж байгаа бол $E$ болон $D$ цэгүүдийг хянах боломжгүй байна.

зураг 1 зураг 2

Худалдан авсан газрыг олон өнцөгт хэлбэртэй гэж үзэх бөгөөд $AB$ хашаа нь $x$ тэнхлэгтэй параллель байхаар координатын тэнхлэгүүдийг сонгосон ба цамхаг барьж болох цэгүүд нь уг шулуун дээр бүхэл тоон цэгүүд байх юм. Жишээлбэл өгөгдсөн зураг 2-т дүрсэлснээр $AB$ дээрх 5 ширхэг бүхэл тоон цэгийн аль нь дээр ч цамхгийг барьж болох юм. Өөрөөр хэлбэл $(4, 8)$, $(5, 8)$, $(6, 8)$, $(7, 8)$ эсвэл $(8, 8)$ гэсэн цэгүүд дээр цамхаг барьж болно. Та худалдан авсан газар нутгийн ямар ч дараалсан 3-н цэгүүд нь нэг шулуун дээр байрлаагүй байна гэж үзэх ба $A$ болон $B$-ээс бусад бүх оройн цэгүүд нь $AB$ хашааны нэг талд оршино гэж үзнэ үү. Өгөгдсөн олон өнцөгт нь өөртэйгөө огтлолцоогүй байна.

Оролт

Эхний мөрөнд оройн тоо $n$ ($3 ≤ n ≤ 1000$) өгөгдөнө.

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

$AB$ хашааны захын цэгүүд нь эхний 2 цэгүүд байх бөгөөд координатууд нь $(x_{1}, y_{1})$ болон $(x_{2}, y_{2})$ байна.

Гаралт

Цамхгууд нь баригдаж болох цэгүүдийн тоог агуулах нэг мөр хэвлэнэ үү.

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

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

Оролт
5
4 8
8 8
9 4
4 0
0 4
Гаралт
5
Оролт
5
4 8
5 8
5 4
7 4
2 2
Гаралт
0

Тэмдэглэл

Зураг 2-т эхний жишээг дүрсэлсэн байна. Зураг дахь бүх цэгүүдийг $AB$ хашааны ямар ч цэгээс хянах боломжтой байх юм. $AB$ нь 5 ширхэг бүхэл тоон координаттай цэгүүд агуулах тул хариулт нь $5$ байна.

2-р жишээний хувьд $CD$ болон $DE$ хашаануудаас гэмт хэрэгтнүүдийг хянах огт боломжгүй байна. Иймд хариулт нь $0$ байна.

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