No.2675 KUMA
Problem Statement
$N$ UMAs (Unidentified Mysterious Animals) live on a two-dimensional coordinate plane. When they are numbered $1, 2, \dots, N$, the $i$-th UMA lives at the lattice point $(x_i, y_i)$ and never moves from there.
To study the UMAs, we have decided to choose any number of points on the coordinate plane and install KMAs (Keima-shaped Monitoring Apparatuses) on them. Each KMA is installed facing one of the four directions east, west, south, or north, independently of the others. When a KMA is placed at point $(a, b)$, the following points become observable through that KMA.
- When facing east, $(a + 2, b - 1)$ and $(a + 2, b + 1)$
- When facing west, $(a - 2, b - 1)$ and $(a - 2, b + 1)$
- When facing south, $(a - 1, b - 2)$ and $(a + 1, b - 2)$
- When facing north, $(a - 1, b + 2)$ and $(a + 1, b + 2)$
However, there are restrictions on the placement of KMAs, and the following conditions must be satisfied.
- A KMA must not be installed at a point where a UMA lives.
- Multiple KMAs cannot be installed at the same point.
Under these conditions, is it possible to make the points where all $N$ UMAs live observable by placing KMAs appropriately? Also, in that case, what is the minimum number of KMAs required?
Constraints
- All inputs are integers
- $1 \leq N \leq 16$
- $0 \leq x_i \leq 1000$
- $0 \leq y_i \leq 1000$
- If $i \neq j$, then $(x_i, y_i) \neq (x_j, y_j)$
Input
The input is given from Standard Input in the following format.
$N$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$
Output
If the points where all $N$ UMAs live can be made observable by placing KMAs appropriately, output the minimum number of KMAs required on one line.
Otherwise, output -1.
Print a newline at the end.
Sample
Sample 1
Input
3 0 3 2 1 2 3
Output
2
For example, installing two KMAs as follows makes all the UMAs observable.
- Install one at point $(-2, 2)$ facing east.
- Install one at point $(4, 2)$ facing west.
Sample 2
Input
9 3 3 5 4 4 5 2 5 1 4 1 2 2 1 4 1 5 2
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Xelmeph
null
ngtkana
eoeo