Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
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)$ цэгүүд дээр байгаа мангасууд юм.