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

#include<cstdio>
#include<cstring>
//#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1e-7
inline double abs(double x)
{
   if(x>0)
     return x;
   return -x;       
}
inline double min(double x,double y)
{
   if(x>y)
    return y;
   return x;       
}
/*
inline int read()
{
   int s=0;
   int f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9')
    {
       if(ch=='-')
        f=-1;
       ch=getchar();                    
    }       
   while(ch>='0'&&ch<='9')
    {
       s=s*10+ch-'0';
       ch=getchar();                      
    }
   return s*f;
}
*/
double x[1010];
double y[1010];
int link[1010][1010];
int dp[1<<(20-1)];
inline void init()
{
   memset(dp,0x3f,sizeof(dp));
   //printf("%d",dp[1]);
   //while(1);
   dp[0]=0;
   memset(x,0,sizeof(x));
   memset(y,0,sizeof(y));
   memset(link,0,sizeof(link));     
}
int main()
{
   freopen("angrybirds.in","r",stdin);
   freopen("angrybirds.out","w",stdout);
   int T;
   scanf("%d",&T);
   while(T--)
    {
       init();
       int n;
       scanf("%d",&n);
       int m;
       scanf("%d",&m); 
       for(int i=1;i<=n;i++)
        {
          scanf("%lf",&x[i]);
          scanf("%lf",&y[i]);
          //y[i]=read();        
        }        
       for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
         {
            
            double a;
            double b;
            if(abs(x[i]-x[j])<=eps)
             continue;
            b=(y[j]-((x[j]*x[j])/(x[i]*x[i]))*y[i])/(x[j]-((x[j]*x[j])/x[i]));
            a=(y[i]-b*x[i])/(x[i]*x[i]); 
            if(a>=-eps)
             continue;
            //printf("%.7lf ",a);
            //printf("%.7lf\n",b);
            for(int k=1;k<=n;k++)
             if(abs((a*x[k]*x[k]+b*x[k])-y[k])<=eps)
              link[i][j]+=1<<(k-1);
            //printf("%d\n",link[i][j]);
         }
       for(int i=0;i<=(1<<n)-1;i++)
        for(int j=1;j<=n;j++)
         {  
           if(!(i&(1<<(j-1))))
            for(int k=j+1;k<=n;k++)
             dp[i|link[j][k]]=min(dp[i|link[j][k]],dp[i]+1);                  
           dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);       
         }       
       printf("%d\n",dp[(1<<n)-1]);
       //printf("\n");
    //while(1);
    } 
   //while(1);   
}
/*
1
4 0
1.18 2.32
2.36 4.64
3.54 6.96
4.72 9.28
*/