追記（2023/1/7）

想定解に不備が見つかったため、本問を「未証明・不備あり問題」に設定いたしました。
皆様にご迷惑をおかけし、誠に申し訳ございません。

また、以下でご指摘いただいたケースをそれぞれ「09_after_contest_01.txt」「09_after_contest_02.txt」「09_after_contest_03.txt」として
テストケースに追加いたしました。ご指摘いただいたhamamu氏、toomer氏に感謝申し上げます。

• https://twitter.com/hamamu_kyopro/status/1611608171348623361?s=20&t=AtIwoxqGveKWz41Jo_opRg

• https://twitter.com/toomerhs/status/1611610210396942336?s=20&t=AtIwoxqGveKWz41Jo_opRg

• https://twitter.com/toomerhs/status/1611614052224217089?s=20&t=AtIwoxqGveKWz41Jo_opRg

追記（2023/1/12）

本問における想定解の不備について、下記に詳細を纏めました。もしよろしければ、ご一読いただけると幸いです。
→ https://maskoats.hatenablog.com/entry/2023/01/12/115331

問題文

二次元平面上に $N$ 個の点 $P_{1}, P_{2}, \dots, P_{N}$ があり、点 $P_{i}$ $(1 \leq i \leq N)$ の座標は $( X_{i}, Y_{i} )$ です。

次の条件を満たす正整数 $n$ の最小値を求めてください。

• この平面上に座標の重複を許して $n+1$ 個の点 $Q_{0}, Q_{1}, \dots, Q_{n}$ を適切に配置したとき、次が成り立つ。

• 任意の整数 $i$ $(1 \leq i \leq N)$ に対してある整数 $j$ $(1 \leq j \leq n)$ が存在し、点 $P_{i}$ が線分 $Q_{j-1} Q_{j}$ （端点を含む）上にある。

制約

• $1 \leq N \leq 12$

• $-100 \leq X_{i}, Y_{i} \leq 100$ $(1 \leq i \leq N)$

• $(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$ $(1 \leq i < j \leq N)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
   $\vdots$
$X_{N}$ $Y_{N}$

• $1$ 行目には $N$ が与えられる

• $(1 + i)$ $(1 \leq i \leq N)$ 行目には $X_{i}$ と $Y_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力してください。

サンプル

6
0 0
2 0
3 1
2 2
0 2
-1 1

3

4
3 1
0 0
5 -2
5 -5

2

1
-100 -100

1

12
5 55
4 49
-1 15
9 86
-2 10
-12 -59
2 40
7 76
10 98
-3 8
8 86
-6 -23

6