問題一覧 > 通常問題

No.2675 KUMA

レベル : / AI推定難易度 : 1425 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 33
作問者 : nu50218 / テスター : Xelmeph null ngtkana NokonoKotlin eoeo
お気に入りにしたユーザー ProblemId : 10646 / 自分の提出
問題文最終更新日: 2024-03-15 21:48:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 421 (NUPC2023) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。