记录编号	608789	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2561.[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	54lku	是否通过	通过
代码语言	C++	运行时间	1.633 s
提交时间	2025-10-29 12:19:13	内存使用	4.08 MiB

#include<bits/stdc++.h>
using namespace std;
int dp[0b111111111111111111];
const long double esp=1e-10;
struct dot
{
    long double x,y;
    dot(){x=y=0;}
    dot(long double a,long double b){x=a;y=b;}
};
struct func
{
    long double a,b;
    int stu;
    func(){a=b=stu=0;}
    func(dot pos1,dot pos2)
    {
        a=(pos2.x*pos1.y-pos1.x*pos2.y)/(pos1.x*pos2.x*(pos1.x-pos2.x));
        b=(pos1.x*pos1.x*pos2.y-pos2.x*pos2.x*pos1.y)/(pos1.x*pos2.x*(pos1.x-pos2.x));
        stu=0;
    }
    bool suitable(dot pos)
    {
        if(fabs(a*pos.x*pos.x+b*pos.x-pos.y)<esp)
            return 1;
        return 0;
    }
};
vector<func> line;vector<dot> pos;
queue<int> q;
int main()
{
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;--n;
        pos.clear();
        line.clear();
        while(!q.empty())q.pop();
        for(int i=0;i<=n;i++)
        {
            long double a,b;
            cin>>a>>b;
            pos.push_back(dot(a,b));
        }
        for(int i=0;i<=(1<<(n+1))-1;i++)
            dp[i]=0;
        for(int i=0;i<=n;i++)
        {
        	func p;
        	p.stu=(1<<i);
        	line.push_back(p);
            for(int j=i+1;j<=n;j++)
            {
            	
                if(fabs(pos[i].x-pos[j].x)<esp)continue;
                func tmp=func(pos[i],pos[j]);
                if(tmp.a>=esp||fabs(tmp.a)<esp)continue;
                for(int k=0;k<=n;k++)
                    if(tmp.suitable(pos[k]))
                        tmp.stu|=(1<<k);
                line.push_back(tmp);
            }
        }
        q.push(0);
        while(!q.empty())
        {
            int p=q.front();q.pop();
            for(int i=0;i<(int)line.size();i++)
            {
                if(!dp[p|line[i].stu])
                {
                    dp[p|line[i].stu]=dp[p]+1;
                    q.push(p|line[i].stu);
                }
            }
        }
        cout<<dp[(1<<(n+1))-1]<<'\n';
    }
}