记录编号	404523	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	2.201 s
提交时间	2017-05-13 18:00:12	内存使用	4.33 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
int t,n,m,pao[5000],f[1<<20],cnt,o=0;
double hz[20],zz[20],x[20],y[20];
int v[20];
int min(int a,int b)
{
    return a<b? a:b;
}
void zb()
{
     double a,b;
     for(int i=1;i<=n;i++)
        scanf("%lf%lf",&hz[i],&zz[i]);
     for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
               if(abs(hz[i]-hz[j])<1e-6)
                   continue;
               a=(zz[i]/hz[i]-zz[j]/hz[j])/(hz[i]-hz[j]);  
               //cout<<a<<endl;
               if(a<-1e-6)
                {//cout<<i<<" "<<j<<" "<<a<<endl;
                   b=zz[i]/hz[i]-hz[i]*a;
                   pao[++cnt]|=1<<(i-1);
                   pao[cnt]|=1<<(j-1);
                   for(int k=1;k<=n;k++)
                   {
                      double g=a*hz[k]+b;
                      if(abs(g-zz[k]/hz[k])<1e-7)
                      {
                          pao[cnt]|=1<<(k-1);
                      }
                   }
                }
        }
}
void work()

{
     scanf("%d%d",&n,&m);
     zb();
     for(int i=1;i<=n;i++)
     {
          //f[1<<(i-1)]=1;
          pao[++cnt]|=(1<<(i-1));
     }
     f[0]=0;
     for(int i=0;i<(1<<n);i++)
     {
         for(int j=1;j<=cnt;j++)
         {
               
                   f[i|pao[j]]=min(f[i]+1,f[i|pao[j]]);
         }    
     }
    // for(int i=0;i<(1<<n);i++)
    //      cout<<f[i]<<endl;
     printf("%d\n",f[(1<<n)-1]);
}
int main()
{
   freopen("angrybirds.in","r",stdin);
    freopen("angrybirds.out","w",stdout);
    cin>>t;
    while(t--)
    {
        memset(f,20,sizeof(f));
        memset(pao,0,sizeof(pao));
        cnt=0;
        work();      
    }
   // while(1);
}