题目略
被奶会挂这题，然而并没有。。。
顺便吐槽一句：这题数据似乎有点水。。。O(n*2^n)最长才50ms。。。。。。
还有。。。m到底是干啥用的。。。全程没用上。。。
下面进入正题：
这道题还是蛮裸的，看一眼n<=18，2s，大概就猜到是O(n*2^n)了（然而后来发现时限是卖萌的）
直接状压不太优雅，而且萌新可能会搞不懂使用以前值的时间逻辑
所以，写递推好了:
d(S)=min(1+d(S'),d(S))
S'就是删去S中编号最小猪及其最多附属猪（可以一起打掉的）后的猪集合
记忆化一下，算d((1<<n)-1)就可以了
需要注意的几点是：
1.当P1,P2,O三点共线时，不可能构成抛物线
2.抛物线的a大于0时，不成立
3.可以单独打一个猪，要加个特判
下面上代码：
1 #include<cstdio> 2 #include<cstring> 3 #define inf 0x3f3f3f3f 4 #define eps 1e-6 5 double sa[19][19],sb[19][19],px[19],py[19],x3,y3; 6 int db[1<<19],n,d[1<<19]; 7 template<typename T> 8 inline void read(T &x){ 9 char ch;while((ch=getchar()),(ch>'9'||ch<'0')); 10 x=ch-'0';while((ch=getchar()),(ch>='0'&&ch<='9')) x=x*10+ch-'0'; 11 } 12 inline double abss(double x){ 13 return x>=0?x:-x; 14 } 15 inline int minn(int a,int b){ 16 return a<b?a:b; 17 } 18 inline bool mat(int i,int j,int k){ 19 if(i==j&&j==k) return true; 20 x3=px[k],y3=py[k]; 21 if(sa[i][j]!=0){ 22 if(sa[i][j]>0) return false; 23 if(abss(x3*x3*sa[i][j]+x3*sb[i][j]-y3)<=eps) return true; 24 else return false; 25 } 26 sa[i][j]=sa[j][i]=(py[i]*px[j]-py[j]*px[i])/(px[i]*px[j]*(px[i]-px[j])); 27 sb[i][j]=sb[j][i]=py[i]/px[i]-(py[i]*px[j]-py[j]*px[i])/(px[j]*(px[i]-px[j])); 28 if(sa[i][j]>0) return false; 29 if(abss(x3*x3*sa[i][j]+x3*sb[i][j]-y3)<=eps) return true; 30 else return false; 31 } 32 int dp(int S){ 33 if(d[S]<19) return d[S]; 34 int i,j,k; 35 int ans; 36 for(i=1;i<=n;++i) if(S&(1<<(i-1))) break; 37 for(j=i;j<=n;++j) 38 if(((S&(1<<(j-1)))&&px[i]!=px[j]&&abss(py[j]/px[j]-py[i]/px[i])>eps)||i==j){ 39 if(i==j){ 40 d[S]=minn(d[S],1+dp(S^(1<<(i-1)))); 41 continue; 42 } 43 ans=S; 44 for(k=i;k<=n;++k) if((S&(1<<(k-1)))&&mat(i,j,k)) ans^=(1<<(k-1)); 45 if(ans!=S) d[S]=minn(1+dp(ans),d[S]); 46 } 47 return d[S]; 48 } 49 int main(){ 50 register int T,m; 51 read(T); 52 memset(db,inf,sizeof db); 53 db[0]=0; 54 for(register int b=0;b<19;++b) db[1<<b]=1; 55 for(register int a=0;a<T;++a){ 56 memcpy(d,db,sizeof d); 57 read(n),read(m); 58 for(register int b=1;b<=n;++b) scanf("%lf%lf",&px[b],&py[b]); 59 printf("%d ",dp((1<<n)-1)); 60 if(a==T-1) return 0; 61 memset(sa,0,sizeof sa); 62 memset(sb,0,sizeof sb); 63 } 64 return 0; 65 }