简要题意：
平面直角坐标系的第一象限有若干绿猪，小鸟要通过若干条函数解析线来消灭它们。每个小鸟可以把所有 (y=ax^2 + bx (a<0)) 上的 ((x,y)) 的所有绿猪消灭，当然没有绿猪就是白走。问最少多少次后可以消灭所有的绿猪。(T) 组数据。
前记
实际上，之前写过一篇 骗分导论，里面有点口出狂言，既然自己说了能 (60pts) 那还不来填坑？
算法一
对于 (70 \%) 的数据，(n leq 12).
实际上，直接爆搜即可。
怎么搜？对于每个搜索状态，你可以用一个 ( ext{vector}) 来记录当前 剩下绿猪的坐标，并记录当前步数。
由于 ( ext{vector}) 可以方便的删除元素，我们枚举当前 ( ext{vector}) 的两个坐标并计算出 (a,b) 的值，然后判断 (a<0)，合法则将所有 (y=ax^2+bx) 上的绿猪删除，进入下一层。
这样的话，如果你没有开 ( ext{long double})，可以得到 (55pts).
开了之后就是 (70pts). 脸黑啊
时间复杂度：(O( ext{70pts})).
期望得分：(60pts). 实际得分：(70pts).
暴力最强大！
算法二
对于 (100 \%) 的数据，(n leq 18)，(T leq 5).
显然，我们会发现在上面的搜索中，冗余的状态太多了。
比方说你先把 (1,4) 一起打下来，再把 (2,3) 一起打下来，和把打它们的顺序换一下，本质有什么区别呢？——没有，但是搜索中会大量出现类似 重复搜索同一个状态 的现象，就会想斐波那契数列那样越滚越大，最终 ( ext{TLE}).
就上面一点而言，假设造个数据，保证每两头绿猪都无法一起打下，即每次只能干掉一个，那这个程序的时间复杂度 (cdots cdots)
所以我们想解决这个问题，但是你认为如果用 ( exttt{map<vector<pair<db,db> > >}) 实在是不好，还多一个 (log)，就和正解阴差阳错了。所以我们想到，记忆化搜索的本质不就是 ( ext{dp})？而枚举状态的 ( ext{dp}) 不就是 (cdots cdots)
状态压缩 ( ext{dp})，简称状压！
我们可以用一个二进制数来表示当前状态（显然只有打下和没打下两个情况），然后先把所有解析线（至少能打下 (2) 头绿猪的）统计在一起，然后枚举状态转移即可。但这个说法不太清晰，需要建立理论模型。
用 (f) 存储状态，(f_0) ~ (f_{{2^n}-1}) 即为所有状态。把当前解析线能消灭的猪也有一个二进制数存在 (s) 里，每次枚举状态的时候，对于每个 (s) 都要考虑一个转移：
f[k|s[i]]=min(f[k|s[i]],f[k]+1);
即如果当前线包含 (i) 则直接用线解决；否则 (+1).
但是你发现会有一些绿猪，只能单独被打，不能和别的猪一起被打。
对于这样的猪，我们需要再枚举所有的猪，将它更新一遍。
f[k|(1<<(i-1))]=min(f[k|(1<<(i-1))],f[k]+1);
显然对于第 (k) 个状态，当前所有猪被打的答案可以直接更新掉，解决了这个问题。
最后(f_{{2^n}-1}) 就是答案。
时间复杂度：(O(2^n cdot n^2)).（不过 ( ext{AThousandSuns}) 提出了一种 (O(2^n cdot n)) 的算法，详见 AThousandSuns 的洛谷博客）
期望得分：(85pts). 实际得分：(100pts).
理论上跑满了约为 (8.4 imes 10^7)，挺危险的，擦边球过去了。
这里你就会明白为什么记忆化搜索过不了，因为，记忆化用 ( ext{map}) 的时间复杂度是 (O(2^n cdot n^2 log n))，你就多了 (4) 倍的常数，成功到了 (2.7 imes 10^8) 一个更危险的级别。当然常数好卡过去我也不说什么了
注意一下：计算解析式的时候可能存在一定精度问题，因此保留 (10^{-6}) 即可。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define db long double
const int N=1e6+1;
inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
inline void write(int x) {
if(x<0) {putchar('-');write(-x);return;}
if(x<10) {putchar(char(x%10+'0'));return;}
write(x/10);putchar(char(x%10+'0'));
}
int n,m,T,cnt=0;
int f[N],s[501];
db x[101],y[101];
int main() {
T=read(); while(T--) {
n=read(),m=read();
memset(f,0x3f,sizeof(f));
memset(s,0,sizeof(s));
cnt=0; f[0]=0; //初始化
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(x[i]-x[j]) {
double a=(y[i]-y[j]*x[i]/x[j])/x[i]/(x[i]-x[j]);
double b=(y[i]*x[j]*x[j]/x[i]/x[i]-y[j])/(x[j]*x[j]/x[i]-x[j]);
if(a<0) { //计算合法的解析式
cnt++;
for(int k=1;k<=n;k++)
if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<=1e-6) s[cnt]|=(1<<(k-1));
} //记录解析式
}
for(int k=0;k<=(1<<n)-1;k++) {
for(int i=1;i<=cnt;i++) f[k|s[i]]=min(f[k|s[i]],f[k]+1);
for(int i=1;i<=n;i++) f[k|(1<<(i-1))]=min(f[k|(1<<(i-1))],f[k]+1);
} printf("%d
",f[(1<<n)-1]);
}
return 0;
}