求助

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int mx=10010;//大于n*o（o<=n*n/2+n） 
int n,m,T;
int o;//有几条抛物线
int out;//答案
const double ok=1e-8;//精度 
inline bool d_d(double a,double b){
    return fabs(a-b)<=ok;
}
struct Pig{
    double x;
    double y;
}pig[20];//小猪 
struct Node{
    double a;
    double b;
    int sum;
    int s[20];//经过的小猪 
}node[401];//抛物线 
int vis[20][20];//哪些猪之间有公共抛物线 
int vip[20];//哪些猪已经被打了 
struct DLX{
    int n,m,cnt;
    int l[mx],r[mx],u[mx],d[mx],row[mx],col[mx];
    int h[mx];
    int s[mx];
    void init(int _n,int _m){
        n=_n,m=_m;
        int i;
        for(i=0;i<=m;i++){
            r[i]=i+1;
            l[i]=i-1;
            u[i]=d[i]=i;
        }
        r[m]=0;
        l[0]=m;
        memset(h,-1,sizeof(h));
        memset(s,0,sizeof(s));
        cnt=m+1;//开始时有m个结点（0结点和各列头结点）
    }//构造n行m列的矩阵 
    inline void link(int R,int C){
        s[C]++;
        row[cnt]=R;
        col[cnt]=C;
        u[cnt]=C;
        d[cnt]=d[C];
        u[d[C]]=cnt;
        d[C]=cnt;
        if(h[R]<0)h[R]=r[cnt]=l[cnt]=cnt;
        else{
            r[cnt]=h[R];
            l[cnt]=l[h[R]];
            r[l[h[R]]]=cnt;
            l[h[R]]=cnt;
        }
        cnt++;
    }//在r行c列插入点
    inline void del(int c){
    	for(int i=d[c];i!=c;i=d[i]){
    		l[r[i]]=l[i],r[l[i]]=r[i];	
    	}	
    }//删除c列 
    inline void res(int c){
        for(int i=u[c];i!=c;i=u[i]){
            l[r[i]]=i,r[l[i]]=i;
        }
    }//恢复c列 
    int leave(){
        int ans=0;
        bool vis[m];
        register int i,j,k;
        memset(vis,0,sizeof(vis));
        for(i=r[0];i!=0;i=r[i]){
            if(vis[i]==0){
                vis[i]=1;
                ans++;
                for(j=d[i];j!=i;j=d[j]){
                    for(k=r[j];k!=j;k=r[k])
                    vis[col[k]]=1;
                }
            }
        }
        return ans;
    }//剩余猪最坏情况用的抛物线数
    void dance(int deep){
        if(deep+leave()>=out)return;//剪枝 
        if(r[0]==0){
            out=deep;
            return;
        }
        int c=r[0];
        register int i,j;
        for(i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;//找到点最少的列
        for(i=d[c];i!=c;i=d[i]){
            del(i);
            for(j=r[i];j!=i;j=r[j])del(j);
            dance(deep+1);
            for(j=l[i];j!=i;j=l[j])res(j);
            res(i);
        }
        return;
    }
}dlx;
int sum[20];
int maxn;//能打最多猪的抛物线打了多少猪 
int co;//单独的猪的数量 
int main(){
    scanf("%d",&T);
    register int i,j,k;
    double x1,x2,y1,y2;
    while(T--){
        out=1<<30;
        maxn=1;
        o=0;
        co=0;
        memset(node,0,sizeof(node));
        memset(sum,0,sizeof(sum));
        memset(vip,0,sizeof(vip));
        memset(vis,0,sizeof(vis));//清除上关的信息 
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)scanf("%lf%lf",&pig[i].x,&pig[i].y);
        for(i=1;i<=n;i++){
            for(j=i+1;j<=n;j++){
            	if(pig[i].x==pig[j].x)continue;
                if(vis[i][j]==1)continue;
                x1=pig[i].x,x2=pig[j].x,y1=pig[i].y,y2=pig[j].y;
                o++;
                node[o].a=(y1*x2-y2*x1)/((x1-x2)*(x1*x2));
                if(node[o].a>0||d_d(node[o].a,0)==1){
                o--;
                continue;
                }
                node[o].b=((y2/x2)-node[o].a*x2);//计算抛物线 
                for(k=1;k<=n;k++){
                    if(d_d(pig[k].y,pig[k].x*pig[k].x*node[o].a+pig[k].x*node[o].b)){
                        node[o].sum++;
                        node[o].s[node[o].sum]=k;
                        vis[i][k]=1;
                        vis[j][k]=1;
                        vis[k][i]=1;
                        vis[k][j]=1;
                        vip[k]=1;
                        maxn=max(maxn,node[o].sum);
                    }
                }//把该抛物线经过的小猪全加入该抛物线的集合中
            }
        }//初始化 	
    for(i=1;i<=n;i++){//有些抛物线只过一只猪 
	if(vip[i]==0)co++;
	sum[i]=sum[i-1]+vip[i];//每个猪实际对应DLX矩阵中的点 
	}
    out=n-co-maxn+1;
    dlx.init(o,n-co);//o个抛物线，n-co个猪 
    for(i=1;i<=o;i++){
        for(j=1;j<=node[i].sum;j++)dlx.link(i,sum[node[i].s[j]]);//把每一条抛物线对应状态插入 
    }
    dlx.dance(0);
    printf("%d\n",out+co);
    }
    return 0;
}