NOIP2016 愤怒的小鸟 [状压DP]

预处理每两个鸟的斜率，然后枚举每个鸟的状态，复杂的n∗2n。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const double eps=1e-10;
int n,m,t,g;
int f[20][20],dp[300000];
double x[20],y[20];
int main(){
    scanf("%d",&t);
    while(t--){
        double a,b;
        scanf("%d%d",&n,&m);
        for(register int i=0;i<n;++i)scanf("%lf%lf",&x[i],&y[i]);
        memset(f,0,sizeof(f)),memset(dp,0x3f,sizeof(dp)),dp[0]=0;
        for(register int i=0;i<n;++i){
            for(register int j=i+1;j<n;++j){
                a=(y[j]*x[i]-x[j]*y[i])/((x[j]-x[i])*x[i]*x[j]);
                b=(y[j]*x[i]*x[i]-y[i]*x[j]*x[j])/((x[i]-x[j])*x[i]*x[j]);
                if(a>=-eps)continue;
                for(register int k=i;k<n;++k)
                    if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<=eps)f[i][j]|=1<<k;
            }
        }
        for(register int s=0;s<(1<<n)-1;++s){
            g=0;
            while(s&(1<<g))g++;
            dp[s|(1<<g)]=min(dp[s|(1<<g)],dp[s]+1);
            for(register int j=g;j<n;++j)
                dp[s|f[g][j]]=min(dp[s|f[g][j]],dp[s]+1);
        }
        printf("%d\n",dp[(1<<n)-1]);
    }
    return 0;
}