題目#
[NOIP2016 提高組] 憤怒的小鳥#
Kiana 最近沉迷於一款神奇的遊戲無法自拔。
簡單來說，這款遊戲是在一個平面上進行的。
有一架彈弓位於 $(0,0)$ 處，每次 Kiana 可以用它向第一象限發射一隻紅色的小鳥，小鳥們的飛行軌跡均為形如 $y=ax^2+bx$ 的曲線，其中 $a,b$ 是 Kiana 指定的參數，且必須滿足 $a < 0$，$a,b$ 都是實數。
當小鳥落回地面（即 $x$ 軸）時，它就會瞬間消失。
在遊戲的某個關卡裡，平面的第一象限中有 $n$ 隻綠色的小豬，其中第 $i$ 隻小豬所在的坐標為 $\left (x_i,y_i \right)$。
如果某隻小鳥的飛行軌跡經過了 $\left (x_i, y_i \right)$，那麼第 $i$ 隻小豬就會被消滅掉，同時小鳥將會沿著原先的軌跡繼續飛行；
如果一隻小鳥的飛行軌跡沒有經過 $\left (x_i, y_i \right)$，那麼這隻小鳥飛行的全过程就不會對第 $i$ 隻小豬產生任何影響。
例如，若兩隻小豬分別位於 $(1,3)$ 和 $(3,3)$，Kiana 可以選擇發射一隻飛行軌跡為 $y=-x^2+4x$ 的小鳥，這樣兩隻小豬就會被這隻小鳥一起消滅。
而這個遊戲的目的，就是透過發射小鳥消滅所有的小豬。
這款神奇遊戲的每個關卡對 Kiana 來說都很難，所以Kiana還輸入了一些神秘的指令，使得自己能更輕鬆地完成這個遊戲。這些指令將在【輸入格式】中詳述。
假設這款遊戲一共有 $T$ 個關卡，現在 Kiana 想知道，對於每一個關卡，至少需要發射多少隻小鳥才能消滅所有的小豬。由於她不會算，所以希望由你告訴她。
輸入格式#
第一行包含一個正整數 $T$，表示遊戲的關卡總數。
下面依次輸入這 $T$ 個關卡的信息。每個關卡第一行包含兩個非負整數 $n,m$，分別表示該關卡中的小豬數量和 Kiana 輸入的神秘指令類型。接下來的 $n$ 行中，第 $i$ 行包含兩個正實數 $x_i,y_i$，表示第 $i$ 隻小豬坐標為 $(x_i,y_i)$。數據保證同一個關卡中不存在兩隻坐標完全相同的小豬。
如果 $m=0$，表示Kiana輸入了一個沒有任何作用的指令。
如果 $m=1$，則這個關卡將會滿足：至多用 $\lceil n/3 + 1 \rceil$ 隻小鳥即可消滅所有小豬。
如果 $m=2$，則這個關卡將會滿足：一定存在一種最優解，其中有一隻小鳥消滅了至少 $\lfloor n/3 \rfloor$ 隻小豬。
保證 $1\leq n \leq 18$，$0\leq m \leq 2$，$0 < x_i,y_i < 10$，輸入中的實數均保留到小數點後兩位。
上文中，符號 $\lceil c \rceil$ 和 $\lfloor c \rfloor$ 分別表示對 $c$ 向上取整和向下取整，例如：$\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。
$(n \leq 18)$
題解#
看到 n 小於等於 18，要麼搜索，要麼狀壓
使用狀壓 dp，設f[S]表示二進制狀態下要撞到狀態為S集合的豬至少要幾次拋物線
預處理出任意兩點組成的拋物線能打到哪些豬
狀態枚舉的時候，~ 根據題解所說～，只需要對每一個狀態集合，枚舉它第一個沒打到的豬即可
因為打豬的順序並不影響結果
問題#
1.double 判斷是否為 0——fabs(x) < eps
2.double 判斷正負正常和 0 比較
3. 循環特別多的時候注意初始化別放錯位置
代碼#
#include<bits/stdc++.h>
using namespace std;
int T, n, m, a, b;
const double eps = 1e-6;
const int N = 19;
double x[N], y[N];
int lg[1 << N];
int lowbit[1 << N];
int f[1 << N];
int curve[N][N];
//int f[1 << N];
void getab(double &a, double &b, double x1, double y1, double x2, double y2)
{
a = (y2 * x1 - y1 * x2)/ (x1 * x2 * (x2 - x1));
b = (y2 * x1 * x1 - y1 * x2 * x2)/ (x1 * x2 * (x1 - x2));
}
int main()
{
for(int i = 2;i <= (1 << 18);i++)
{
lg[i] = lg[i >> 1] + 1;
}
for(int i = 0;i < (1 << 18);i++)
{
lowbit[i] = (~i & (-(~i)));
}
scanf("%d", &T);
while(T --)
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i++)
{
scanf("%lf%lf", &x[i], &y[i]);
}
double a, b;
memset(f, 0x3f, sizeof f);
memset(curve, 0, sizeof curve);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
if(i == j || fabs(x[i] - x[j]) < eps) continue;
getab(a, b, x[i], y[i], x[j], y[j]);
if(a > 0) continue;
for(int k = 1;k <= n;k++)
{
if(fabs(a * x[k] * x[k] + b * x[k] - y[k]) < eps)
{
curve[i][j] |= (1 << (k - 1));
// cout << "qwq " << i <<"and"<< j << "shares" << k<< " "<< curve[i][j]<<endl;
}
}
}
}
for(int i = 1;i <= n;i++)
curve[i][i] = (1 << (i - 1));
f[0] = 0;
for(int s = 0;s < (1 << n) - 1;s++)
{
for(int j = 1;j <= n;j++)
{
f[s | curve[lg[lowbit[s]] + 1][j]] = min(f[s | curve[lg[lowbit[s]] + 1][j]], f[s] + 1);
}
}
printf("%d\n", f[(1 << n) - 1]);
}
return 0;
}