【正经题解】愤怒的小鸟

$g$ [ $x$ ]表示二进制编码为 $x$ 的状态所用的最小步数。
$sol$ [ $i$ ]表示第 $i$ 组解。解共有 $s$ 组。
二进制编码：
状压 $DP$ 基本概念，二进制数每一位的 $1$ 表示可以达到这个点， $0$ 表示不能达到这个点。
比如， $g$ [ $10101001$ ]（二进制）表示达到第 $1$ ， $4$ ， $6$ ， $8$ 个点（十进制）所用的最少抛物线数。
解： 能通过仅 $1$ 条抛物线所达到的所有的点组成的二进制编码，叫做一个解。
本题主要分为以下几步：
预处理。此处可用递归。首先枚举两个点，通过两个点共抛物线构造二元一次方程，用公式将其解出。
公式： $a1x+b1y=c1$ , $a2x+b2y=c2$ ,解得 $x$ $=$ ( $b2$ * $c1-b1$ * $c2$ )/( $a1$ * $b2-a2$ * $b1$ ), $y$ $=$ ( $a1$ * $c2-a2$ * $c1$ )/( $a1$ * $b2-a2$ * $b1$ ).
$DP$ 。此处可以理解为 $01$ 背包。背包容量为( $1<<n$ ) $-1$ ，共 $s$ 个物品，费用分别为 $sol$ [ $1$ ], $sol$ [ $2$ ],..., $sol$ [ $s$ ]，价值均为 $1$ ，且要求把背包装满，求最小价值。
但是有一个极大的漏洞：比如我们要配出（以下均为二进制） $10011000$ 这个数，一种正确的配法是 $10000000+00011000$ ，但是另 一种拼法是 $10000000+00010111+00000001$ ，发生了进位，虽然和依然是 $10011000$ ，但是第 $1$ 个点显然被打了 $2$ 次。
改进方法：另加一重循环，判断是否有重复。时间复杂度 $O$ ( $n$ )
本步总时间复杂度： $O$ ( $smn$ )，其中 $m=1<<n$ ，可以证明 $s<=n$ ^ $2$ / $2$ ，故复杂度 $O$ ( $2$ ^ $n$ * $n$ ^ $3$ )，期望得分 $75$ ~ $85$ 分。
优化 不难发现，比如一条抛物线恰好打中了 $1$ ， $4$ ， $6$ ， $8$ （均为十进制）这四个点，且不能打中其他的点。则这条抛物 线使 $s$ 的值增加了 $15$ （即( $1$ ),( $4$ ),( $6$ ),( $8$ ),( $1$ , $4$ ),( $1$ , $6$ ),( $1$ , $8$ ),( $4$ , $6$ ),( $4$ , $8$ ),( $6$ , $8$ ),( $1$ , $4$ , $6$ ),( $1$ , $4$ , $8$ ),( $1$ , $6$ , $8$ ),( $4$ , $6$ , $8$ ),( $1$ , $4$ , $6$ , $8$ ).事实上，由于我们是用最少的抛物线打最多的点，因此最后一种( $1$ , $4$ , $6$ , $8$ )的方案比前 $14$ 种的任意一种都更优。因此，只需在无法继续递归（即没有其他点可以打）时将方案添加到 $sol$ [ $s$ ]中，很大程度上降低了 $s$ 的大小。（但 并不能改变最坏复杂度，因为有可能特造一数据使得无任意三点共抛物线）
最重要的优化：我们在背包中进行位运算判断是否重复，因此添加了重复的情况还要舍去，多一维复杂度。不妨逆向思考： $g$ [ $j$ ] $=min$ ( $g$ [ $j$ ], $g$ [ $j-sol$ [ $i$ ] $+1$ ),原来可以用要更新的点 $j$ 的编号来表示用来更新此点的点 $j-sol$ [ $i$ ]，现在可以用用来更新此点的点的编号来表示此点。即用 $g$ [ $j$ ]来更新其他点，而不是用其他点来更新 $g$ [ $j$ ].这样，我们就可以写出被更新的点的编号： $g$ [ $i$ | $sol$ [ $j$ ]].
注意：二进制原来 $1+1=10$ ，现在 $1$ | $1=1$ ，不会发生进位，因此无需特判，减小一维复杂度。

#include<cstdio>
#include<cstring>
#include<cmath> 
using namespace std;

const int MAXN = 18;
const int MAXM = 262144;
struct Point
{
    double x,y;
};
Point nd[MAXN+2];
int sol[MAXN*MAXN+MAXN];
int g[MAXM+2];
int n,m,c,s;

void solve(double a1,double b1,double c1,double a2,double b2,double c2,double *ansx,double *ansy)
{
    if(a1*b2 != a2*b1)
    {
        *ansx = (b2*c1-b1*c2)/(a1*b2-a2*b1);
        *ansy = (a1*c2-a2*c1)/(a1*b2-a2*b1);
    }
}

void DFS(int pos,int cod,double a,double b)
{
    int i,j;
    double arga,argb;

    if(pos == n) return;
    if(cod == 0)
    {
        for(i=0; i<n; i++)
        {
            for(j=i+1; j<n; j++)
            {
                if(nd[i].x != nd[j].x)
                {
                    solve(nd[i].x*nd[i].x,nd[i].x,nd[i].y,nd[j].x*nd[j].x,nd[j].x,nd[j].y,&arga,&argb);
                    if(arga < -1e-6)
                    {
                        DFS(j,(1<<i)+(1<<j),arga,argb);
                    }
                }
            }
        }
    }
    else
    {
        for(i=pos+1; i<n; i++)
        {
            if(fabs(nd[i].x*nd[i].x*a+nd[i].x*b-nd[i].y) < 1e-12)
            {
                DFS(i,cod+(1<<i),a,b);
                return;
            }
        }
        sol[s] = cod;
        g[cod] = 1;
        s++;
    }
}

bool match(int spos,int gpos)
{
    int i;
    for(i=n-1; i>=0; i--)
    {
        if((sol[spos]&(1<<i)) && (gpos&(1<<i))) return false;
    }
    return true;
}

int main()
{
    int t,i,j;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&c);
        m = 1<<n;
        for(i=0; i<n; i++)
        {
            scanf("%lf%lf",&nd[i].x,&nd[i].y);
        }
        
        if(n == 1)
        {
            printf("1\n");
            continue;
        }
        memset(g,42,sizeof(g));
        memset(sol,0,sizeof(sol));
        s = 0;
        for(i=0; i<n; i++)
        {
            sol[s++] = 1<<i;
            g[1<<i] = 1;
        }
        DFS(0,0,0.0,0.0);

        g[0] = 0;
        for(j=0; j<s; j++)
        {
            for(i=0; i<m; i++)
            {
                if(g[i|sol[j]] > g[i]+1) g[i|sol[j]] = g[i]+1;
            }
        }

        printf("%d\n",g[m-1]);
    }

    return 0;
}