当年的两个压轴题现在都随便做了呢 =w=
原题：
n<=18，t<=5
我当时怎么就不会 系列233
一看这数据范围，欸呀
壮鸭低劈
预处理出任意两个猪能够确定的抛物线方程，最多只有153个，然后检查他们能够扫到哪些猪，把这些猪压二进制压进整数
第i个二进制位为1就表示第i只猪能被扫到
注意还有一只鸟打一只猪的情况，也要处理出来放到一起
最初想的是直接dfs枚举每条边是否要选，但是边数很多，事情并不简单
但其实也不需要搜索，DP就行233
f[i][j]表示直到第i个抛物线，打掉猪的子集j需要的最小代价
实际上开f数组的时候i这一维完全不用，因为二进制压位操作中或操作的特性，也不需要像背包那样必须从大到小转移
只需先枚举每一条抛物线i，再枚举每一个子集j，f[j|b[i]]=min(f[j|b[i]],f[j]+1)即可
抛物线总数不超过200，2^n最多只有262144
所以直接n^2*2^n dp就可以了233
注意一些细节：
1.题目要求a<0，注意判断
2.浮点数判断是abs(a-b)<eps而不是a-b<eps，太久没写忘了233
3.注意一只鸟只打一只猪的情况也要预处理，因为可能存在没有一头猪能够和别的猪凑成a<0的抛物线的情况
我现在去打16NOIP岂不是就是600到手233
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 #define LL long long 8 const double eps=1e-6; 9 const int oo=1000000007; 10 struct nds{double x,y;}a[20]; 11 int n; int N; 12 int b[200],btp=0; 13 int f[262144]; 14 void prvs(){ 15 btp=0; 16 } 17 int main(){ 18 //freopen("ddd.in","r",stdin); 19 int T; cin>>T; 20 while(T --> 0){ 21 int p; 22 scanf("%d%d",&n,&p); prvs(); 23 N=(1<<n)-1; 24 for(int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y); 25 for(int i=1;i<n;++i)for(int j=i+1;j<=n;++j)if(abs(a[i].x-a[j].x)>eps){ 26 double tma=(a[j].y-a[i].y*a[j].x/a[i].x)/(a[j].x*(a[j].x-a[i].x)); 27 double tmb=a[i].y/a[i].x-a[i].x*tma; 28 if(tma<0){ //注意要求 29 b[++btp]=0; 30 for(int k=1;k<=n;++k)if(abs(a[k].x*a[k].x*tma+a[k].x*tmb-a[k].y)<eps) 31 //注意abs 32 b[btp]|=(1<<(k-1)); 33 } 34 } 35 for(int i=1;i<=n;++i) b[++btp]=(1<<(i-1)); 36 //注意有可能不存在可以配对的点 37 for(int i=1;i<=N;++i) f[i]=oo; 38 f[0]=0; 39 for(int i=1;i<=btp;++i)for(int j=0;j<=N;++j) 40 f[j|b[i]]=min(f[j|b[i]],f[j]+1); 41 printf("%d\n",f[N]); 42 } 43 return 0; 44 }