记录编号	608861	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2561.[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	我常常追忆未来	是否通过	通过
代码语言	C++	运行时间	2.560 s
提交时间	2025-10-29 21:25:31	内存使用	7.81 MiB

#include <bits/stdc++.h>
using namespace std;
const double esp=1e-10;
const int N=20;
int f[1<<N];
int de[N*N];
int n,t,m;
struct pig{
    double x,y;
}p[N];
int main(){
    cin>>t;
    while(t--){
        int cnt=0;
        cin>>n>>m;
        memset(f,0x3f,sizeof(f));
        memset(p,0,sizeof(p));
        memset(de,0,sizeof(de));
        f[0]=0;
        for(int i=1;i<=n;i++){
            cin>>p[i].x>>p[i].y;
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(fabs(p[i].x-p[j].x)<esp){
                    continue;
                }
                double aa=(p[i].y*p[j].x-p[j].y*p[i].x)/(p[i].x*p[i].x*p[j].x-p[j].x*p[j].x*p[i].x);
                double bb=(p[i].y-aa*p[i].x*p[i].x)/p[i].x;
                if(fabs(aa)>=esp&&aa<0){
                    cnt++;
                    for(int k=1;k<=n;k++){
                        if(fabs(aa*p[k].x*p[k].x+bb*p[k].x-p[k].y)<=esp){
                            de[cnt]|=(1<<(k-1));
                        }
                    }
                }
            }
        }
        for(int i=0;i<(1<<n);i++){
            for(int j=1;j<=cnt;j++){
                f[i|de[j]]=min(f[i|de[j]],f[i]+1);
            }
            for(int j=1;j<=n;j++){
                f[i|1<<(j-1)]=min(f[i|(1<<(j-1))],f[i]+1);
            }            
        }
        cout<<f[(1<<n)-1]<<"\n";
    }
    return 0;
}