D. Лимак ба харвалтын цэгүүд

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

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

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

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

Бийрлэнд бол аюултай газар. Лимак энд явган аялаж чадахгүй. Түүний оронд түүнд $k$ ширхэг шидэт шилжүүлэгч чулуу байна. Чулуу бүрийг хамгийн ихдээ нэг удаа ашиглаж болно. $i$-р чулуугаар $(ax_{i}, ay_{i})$ цэгрүү шилжиж болно. Лимак чулуунуудыг дурын дарааллаар ашиглаж болно.

Бийрлэндэд $n$ мангас байх ба $i$-р манагас нь $(mx_{i}, my_{i})$ цэг дээр байна.

Өгөгдсөн $k + n$ цэгүүд нь ялгаатай.

Шилжилт бүрийн дараа Лимак аль нэг чиглэлд сум харваж болно. Сум сонгосон чиглэлийн эхний мангасыг ононо. Тэгээд сум, мангас хоёр хоёулаа алга болно. Нэг газартаа удаан байх нь аюултай ба Лимак нэг газраас нэг л удаа харвана.

Хэрвээ Лимак мангасыг онох боломжтой байвал мангас айх ёстой. Хэдэн мангас Лимакаас айх ёстой вэ?

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $k$ ба $n$ ($1 ≤ k ≤ 7$, $1 ≤ n ≤ 1000$) байх буюу чулуу болон мангасуудын тоо юм.

Дараагийн $k$ мөрүүдийн $i$-р мөрд хоёр бүхэл тоо $ax_{i}$ ба $ay_{i}$ ($ - 10^{9} ≤ ax_{i}, ay_{i} ≤ 10^{9}$) байх ба $i$-р чулууг ашиглаад Лимакийн шилжиж чадах цэгийн координатууд юм.

Сүүлийн $n$ мөрийн $i$-р мөрөнд хоёр бүхэл тоо $mx_{i}$ ба $my_{i}$ ($ - 10^{9} ≤ mx_{i}, my_{i} ≤ 10^{9}$) байх буюу $i$-р мангасын координатууд юм.

Гаралт

Лимакаас айх ёстой мангасуудын тоог хэвлэ.

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

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

Оролт
2 4
-2 -1
4 5
4 2
2 1
4 -1
1 -1
Гаралт
3
Оролт
3 8
10 20
0 0
20 40
300 600
30 60
170 340
50 100
28 56
90 180
-4 -8
-1 -2
Гаралт
5

Тэмдэглэл

Эхний жишээн дээр хоёр чулуу, дөрвөн мангас байна. Чулуунуудыг ашиглан доорх зурагт хөхөөр тэмдэглэсэн $( - 2,  - 1)$ ба $(4, 5)$ цэгүүдрүү очиж болно. Мангасууд улаанаар тэмдэглэсэн $(4, 2)$, $(2, 1)$, $(4,  - 1)$ ба $(1,  - 1)$ цэгүүд дээр байна. Лимак $(4,  - 1)$ цэг дээр байгаа мангасыг онох боломжгүй учир энэ мангас Лимакаас айх ёсгүй. Бусад гурван мангасыг онох боломжтой, тиймээс хариу $3$ байна.

Хоёр дахь жишээн дээр таван мангас Лимакаас айх ёстой. Аюулгүй мангасууд нь $(300, 600)$, $(170, 340)$ ба $(90, 180)$ цэгүүд дээр байгаа мангасууд юм.

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