【题意】

【算法】状态压缩型DP

【题解】看数据范围大概能猜到是状压了。

根据三点确定一条抛物线，枚举两个点之间的抛物线，再枚举有多少点在抛物线上（压缩为状态c[]），这样预处理出至多n*n/2+n条抛物线。（注意加上只经过一点的抛物线）

然后f[i]表示猪的消灭状态为i的最小步数，转移方程：f[i&c[j]]=min(f[i&c[j]],f[i]+1)。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxN=300000,maxn=500;const double eps=1e-8;int c[maxn],f[maxN],n,tot,qaq;double x[30],y[30],a[maxn],b[maxn];int main(){    int T=read();    while(T--){        n=read();qaq=read();tot=0;        for(int i=0;i
           
            0){tot--;continue;} c[tot]=(1<
            
             <