| Codeforces Round 363 (Div. 1) |
|---|
| Закончено |
Беарляндия — очень опасное место, поэтому Лимак никогда не ходит пешком. Вместо этого он использует камни телепортации. Всего у него k таких камней, i-й из которых позволяет мгновенно переместиться в точку (axi, ayi). Каждый камень может быть использован не более одного раза, при этом использовать камни можно в любом порядке.
В Берляндии живут n монстров. Монстр с номером i расположен в точке с координатами (mxi, myi). Гарантируется, что позиции всех k + n точек различны.
После каждой телепортации Лимак может выпустить стрелу в произвольном направлении. Стрела убьёт первого монстра, который будет на её пути, после чего и стрела, и монстр исчезнут с карты. Поскольку оставаться на одном месте опасно, Лимак может выпустить не более одной стрелы с каждой позиции.
Монстр опасается Лимака, если существует последовательность действий, при которой Лимак убивает данного конкретного монстра. Вычислите, сколько монстров должны опасаться Лимака?
В первой строке входных данных записаны два числа k и n (1 ≤ k ≤ 7, 1 ≤ n ≤ 1000) — количество камней телепортации и монстров на карте соответственно.
В i-й из последующих k строк записаны два целых числа axi и ayi ( - 109 ≤ axi, ayi ≤ 109) — координаты точки, в которую переместится Лимак при использовании i-го камня.
В i-й из последующих n строк записаны два целых числа mxi и myi ( - 109 ≤ mxi, myi ≤ 109) — координаты i-го монстра.
Гарантируется, что все k + n точек попарно различны.
Выведите количество монстров, которым стоит опасаться Лимака.
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).
