记录编号	405107	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	1.610 s
提交时间	2017-05-15 17:19:27	内存使用	1.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define pp 0.000001
int t,n,m,kk[20][20],f[(1<<18)+5];
double x[20],y[20];
inline double oo(double x){
  if(x<0) return (-x);
  else return x;
}
inline void init(){
   memset(kk,0,sizeof(kk));
   for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++){
      if(oo(x[i]-x[j])<=0.000001) continue;
      double a=(x[i]*y[j]-x[j]*y[i])/(x[i]*x[j]*x[j]-x[i]*x[i]*x[j]);
      double b=(y[i]*x[j]*x[j]-y[j]*x[i]*x[i])/(x[i]*x[j]*x[j]-x[j]*x[i]*x[i]);
      if(a>=-0.000001) continue;
      for(int k=1;k<=n;k++)
       if(oo(a*x[k]*x[k]+b*x[k]-y[k])<=0.000001)
        kk[i][j]|=(1<<(k-1));
      }   
}
inline void dp(){
    memset(f,0x7f,sizeof(f));
    f[0]=0;
    for(int r=0;r<(1<<n);r++)
     for(int i=1;i<=n;i++)
      if(!(r&(1<<(i-1)))){ //!!状态不包含当前鸟 
       for(int j=i;j<=n;j++){
         int temp=r|kk[i][j];
         f[temp]=min(f[temp],f[r]+1);
       }
       f[r|(1<<(i-1))]=min(f[r|(1<<(i-1))],f[r]+1);
       //转移当前状态否则如果单个单个数则无法处理
       //如例2 第一个点两个鸟无法构成一个抛物线图像！！！ 
      } 
    /*for(int i=0;i<(1<<n);i++)
     cout<<f[i]<<endl;
    cout<<endl;*/
    //if(f[(1<<n)-1]>=2130000000) printf("%d\n",n);
    printf("%d\n",f[(1<<n)-1]);
}
int main(){
   freopen("angrybirds.in","r",stdin);
   freopen("angrybirds.out","w",stdout);
   scanf("%d",&t);
   while(t--){
     scanf("%d%d",&n,&m);   
     for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
     init(); 
     /*for(int i=0;i<=n;i++)
      for(int j=i+1;j<=n;j++)
       cout<<kk[i][j]<<endl;*/
     dp();
   }
  // while(1);
   return 0;
}