憤怒的小鳥（滿分版）

// 多組資料應該初始化

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const double eps=1e-8;

inline int read(){

    int num=0,f=1; char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-') f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();

    return num;

}

double x[25],y[25];

int dp[(1<<19)],p[25][25],t,n,m;;

void dfs(int y,int z){

    if(dp[y]!=-1&&dp[y]<=z) return;

    dp[y]=z;

    if(y==(1<<n)-1) return ;

    for(int i=1;i<=n;i++){

        if(y&(1<<(i-1))) continue;

        for(int j=i+1;j<=n;j++){

            if(y&(1<<(j-1))) continue;

            if(p[i][j]==0) continue;

            dfs((y|p[i][j]),z+1);

        }

    }

    for(int i=1;i<=n;i++){

        if(!(y&(1<<(i-1)))){

            dfs(y|(1<<(i-1)),z+1);

        }

    }

}

int main(){

    scanf("%d",&t);

    while(t--){

        n=read(),m=read();

        for(int i=0;i<(1<<19);i++) dp[i]=-1;

        for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);

        for(int i=1;i<=n;i++){

            for(int j=i+1;j<=n;j++){

                 double a=(y[i]/x[i]-y[j]/x[j])/(x[i]-x[j]),

                    b=y[i]/x[i]-a*x[i];

                p[i][j]=0;

                if(a<-eps)

                    for(int k=1;k<=n;k++){

                        if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps){

                            p[i][j]|=(1<<(k-1));

                        }

                    }

            }

        }

        dfs(0,0);

        printf("%d\n",dp[(1<<n)-1]);

    }

    return 0;

}