lp2831 NOIP2016 愤怒的小鸟

看到\(n<=18\)，很容易可以想到状压\(DP\)。
最大力的做法就是，枚举原集合和转移的目的集合，然后考虑一条抛物线能否穿过其中的所有点。
但是这样的复杂度显然是不可接受的，考虑优化。
易知，三点确定一条抛物线，故而在给定\(c=0\)的时候，确定两点即可确定第三点。具体的方程组是：
$$a=\frac{x_{j}*y_{i}-x_{i}*y{j}}{x_{i}*x_{j}*(x_{i}-x_{j})}$$
$$b=\frac{y_{i}}{x_{i}}-a*x_{i}$$
从而我们可以预处理出，通过某两个点的抛物线通过的点的集合，然后对于每一个状态，选择哪两个点拓展即可。
但这个时候的时间复杂度是\(O(T*n^2*2^n)\)，对于较大的数据还是很难通过的。
这时候我们可以发现，第一个选择的点是可以固定的，也就是第一个可选择的点。因为如果选择其他点开始拓展的话，到最后依然要拓展那个点。
那么就成功地将复杂度压缩到了\(O(T*n*2^n)\)，这时候就可以通过了。
PS:凡是Double的题都应该注意精度。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define eps 1E-6
int n,m;
int f[1<<18],A[20][20];
double x[20],y[20];
inline int lwbt(const int &_X){
    return _X&-_X;
}
inline int Min(const int &_X,const int &_Y){
    return _X<_Y?_X:_Y;
}
inline int cnt(int _X){
    int rt=0;
    while(_X&1){
        ++rt;
        _X>>=1;
    }
    return rt;
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        scanf("%lf%lf",&x[i],&y[i]);
    }
    double a,b;
    for(int i=0;i<n;++i){
        for(int j=i;j<n;++j){
            if(x[i]-x[j]<=eps&&x[i]-x[j]>=-eps){
                if(!(y[i]-y[j]<=eps&&y[i]-y[j]>=-eps)){
                    A[i][j]=0;
                    continue;
                }else{
                    A[i][j]=(1<<i)|(1<<j);
                    continue;
                }
            }
            a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
            b=y[i]/x[i]-a*x[i];
            A[i][j]=0;
            if(a>=-eps){
                continue;
            }
            for(int k=0;k<n;++k){
                if(a*x[k]*x[k]+b*x[k]-y[k]<=eps&&a*x[k]*x[k]+b*x[k]-y[k]>=-eps){
                    A[i][j]|=(1<<k);
                }
            }
        }
    }
    /*
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            printf("%d ",A[i][j]);
        }
        puts("");
    }
    */
    const int MAX=1<<n;
    int loc;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    
    for(int i=0;i<MAX;++i){
        loc=cnt(i);
        for(int j=loc;j<n;++j){
            f[i|A[loc][j]]=Min(f[i|A[loc][j]],f[i]+1);
        }
    }
    printf("%d\n",f[MAX-1]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}