记录编号	442347	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	1.018 s
提交时间	2017-08-26 20:48:10	内存使用	2.33 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=20;
const double eps=1e-10;
int T,n,m,t,bin[maxn];
double x[maxn],y[maxn],a,b;
int f[1<<19|2],g[5005],top;
bool judge(double a,double b){return abs(a-b)<eps;}
void work(){
        memset(g,0,sizeof(g));top=0;
        for(int i=1;i<=n;i++)g[++top]=bin[i-1];
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                if(judge(x[i],x[j]))continue;
                a=(y[j]/x[j]-y[i]/x[i])/(x[j]-x[i]);
                if(a>=-eps)continue;
                b=y[i]/x[i]-a*x[i];
                for(int k=1;k<=n;k++)
                    if(judge(a*x[k]+b,y[k]/x[k])){
                      if(k<i)break;
                      if(k==i)top++;
                      g[top]|=bin[k-1];
                    }
            }
        memset(f,0x3f,sizeof(f));
        f[0]=0;
        //for(int i=1;i<=top;i++)printf("%d  %d\n",i,g[i]);
        for(int i=0;i<=bin[n]-1;i++)
            for(int j=1;j<=top;j++)
                  f[i|g[j]]=min(f[i|g[j]],f[i]+1);
        printf("%d\n",f[bin[n]-1]);
}
int main()
{
  freopen("angrybirds.in","r",stdin);
  freopen("angrybirds.out","w",stdout);
    scanf("%d",&T);
    bin[0]=1;
    for(int i=1;i<=19;i++)bin[i]=bin[i-1]<<1;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
        work();
    } 
    return 0;
}