Big Brother and Angry Birds

題目敘述

傳說中，資工系B06中有一位樣樣精通的高手，韋恩．熱狗。聽說他曾經拿過數學物理資訊三項奧林匹亞的金牌，LOL打到菁英，爐石傳說前百，還是某冠軍籃球隊伍的隊長，因此有著大哥的頭銜。今天大哥要來挑戰一個遊戲，相信大家都不陌生的，憤怒鳥（Angry Birds）。這個遊戲中的畫面是一個二維的座標平面，在原點處有一個彈弓，且平面上有$n$隻豬，這些豬都落在第一象限的格子點$(x,y)$上（格子點：$x$座標與$y$座標都是整數的點）。玩家每一次可以用彈弓發射一隻小紅鳥，鳥的軌跡如同現實生活中一般，會是一個通過原點且開口向下的拋物線。正式的來說，一隻鳥的軌跡會是一個$y=ax^2+bx$的拋物線中$x,y \ge 0$的部分，且$a<0$。每次發射小紅鳥時，座標落在拋物線上的所有小豬都會被消滅。注意，為了簡化問題，我們當作小紅鳥和小豬都是質點，沒有體積，且撞到豬後小紅鳥的軌跡不會產生任何變化。

給定平面上$n$隻豬的位置，大哥想要知道，最少要發射幾隻小鳥才能把小豬都消滅呢？

舉例來說，平面上有7隻豬，座標分別為$(1,3),(2,4),(3,3),(2,6),(4,8),(1,1),(1,2)$

則我們最少要發射4隻小鳥：

(1)發射一條軌跡為$y=-x^2+4x$的小鳥，可以消滅位於$(1,3),(2,4),(3,3)$的三隻小豬

(2)發射一條軌跡為$y=-\frac{1}{2}x^2+4x$的小鳥，可以消滅位於$(2,6),(4,8)$的兩隻小豬

(3)發射一條軌跡為$y=-x^2+3x$的小鳥，可以消滅位於$(1,2)$的小豬

(4)發射一條軌跡為$y=-880300x^2+880301x$的小鳥，可以消滅位於$(1,1)$的小豬

因此答案為4。

輸入說明

第一行有一個數字$T$代表共有$T$組測試資料。( $T \leq 3$ )

每一筆測試資料中：

第一行有一個數字$n$，代表平面上的小豬數量。( $1 \leq n \leq 22$ )

接下來有$n$行，每一行有兩個數字$x_i,y_i$，代表第$i$隻小豬的座標為$(x_i,y_i)$。( $1 \leq x_i,y_i \leq 1000$ )

保證不會有兩隻小豬的座標相同。

輸出說明

輸出有$T$行，第$i$行請輸出一個數字代表在第$i$筆測試資料中，最少要發射幾隻小鳥才能消滅所有小豬。

範例測資

範例輸入

2

7

1 3

2 4

3 3

2 6

4 8

1 1

1 2

6

1 8

2 12

3 12

4 4

5 5

6 6

範例輸出

4

3

子任務

1.子任務1 (3pts)

$n=2$

2.子任務2 (7pts)

每次都發射能夠消滅當前最多隻小豬的任何一條軌跡，就會得到最少的發射次數。

3.子任務3 (20pts)

$n \leq 12$

4.子任務4 (20pts)

$n \leq 18$ 且保證初始狀態沒有任何一條發射的軌跡可以消滅超過兩隻鳥

5.子任務5 (25pts)

$n \leq 18$

6.子任務6 (25pts)

無特殊條件

6.子任務extra (5pts)

$x_i,y_i$的範圍更動：$1 \leq x_i,y_i \leq 10^{9}$