P2831 愤怒的小鸟——状压

P2831 愤怒的小鸟

抛物线过原点，只要再找两个就能确定抛物线；

处理出两两之间的抛物线能过哪些点，状态压缩；

但是直接枚举每一条抛物线常数太大会T，所以我们需要预处理一个low_bit表示当前状态下第一个没选的，即是二进制下第一个不是1的位置；

因为我们早晚都要把它变成1，所以先处理他就可以达到要求；

注意精度问题；

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef double dd;

const int maxn=;

const dd acc=1e-;

int T,n,m;

dd x[maxn],y[maxn];

int low_bit[<<];

int line[maxn][maxn];

void check(dd&a,dd &b,dd x1,dd y1,dd x2,dd y2)

{

    a=(y1*x2-y2*x1)/(x1*(x1*x2-x2*x2));

    b=(y2-a*x2*x2)/x2;

}

int f[<<];

int main()

{

    for(int i=;i<<<;i++)

    {

        int j=;

        for(;j<=&& i&(<<(j-));j++);

        low_bit[i]=j;

        //printf("!!%d\n",low_bit[i]);

    }

    scanf("%d",&T);

    while(T--)

    {

        memset(f,0x3f,sizeof(f));

        memset(line,,sizeof(line));

        f[]=;

        scanf("%d%d",&n,&m);

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

        {

            scanf("%lf%lf",&x[i],&y[i]);

        }

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

        {

            for(int j=;j<=n;j++)

            {

                if(fabs(x[i]-x[j])<acc) continue;

                dd a,b;

                check(a,b,x[i],y[i],x[j],y[j]);

                //printf("!!\n");

                //printf("%lf %lf\n",a,b);

                if(a>-acc) continue;

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

                {

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

                    {

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

                        //printf("!!%d\n",line[i][j]);

                    }

                }

            }

        }

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

        {

            int j=low_bit[i];

            //printf("!?%d\n",j);

            f[i|(<<(j-))]=min(f[i]+,f[i|(<<(j-))]);

            //printf("??%d\n",f[i|(1<<(j-1))]);

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

            {

                f[i|line[j][k]]=min(f[i]+,f[i|line[j][k]]);

            }

        }

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

    }

    return ;

}