#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>

using namespace std;

void read(int &x) {
    char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = x*10+c-'0';
    flag?x=-x:x;
}

#define eps (1e-7)

int n,m;
double x[20],y[20];
int s[20][20],f[(1<<18)+10];

const bool dcmp(const double a,const double b) {
    return fabs(a-b) < eps;
}

void work() {
    read(n); read(m);
    memset(f,127/3,sizeof f);
    memset(s,0,sizeof s);
    for (int i = 1; i <= n; i++)
    scanf("%lf%lf",&x[i],&y[i]);
    for (int i = 1; i <= n; i++)
     for (int j = i+1; j <= n; j++)
      if (i != j) {
          if(x[i] == x[j] && y[i] != y[j]) continue;
          double a = (y[j]*x[i]/x[j]-y[i])/(x[i]*x[j]-x[i]*x[i]),b = (y[i]-a*x[i]*x[i])/x[i];
          if(a >= 0 || dcmp(a,0)) continue;
          s[i][j] = (1<<i-1)|(1<<j-1);
          for (int k = 1; k <= n; k++)
            if(k != i && k != j) {
               double aa = (y[k]*x[i]/x[k]-y[i])/(x[i]*x[k]-x[i]*x[i]),bb = (y[i]-a*x[i]*x[i])/x[i];
               if(dcmp(aa,a) && dcmp(bb,b)) s[i][j] |= (1<<k-1);
            }
          s[j][i] = s[i][j];
      }
    for (int i = 1; i <= n; i++) s[i][i] |= (1<<i-1);
    f[0] = 0;
    for (int t = 0; t < (1<<n)-1; t++)
      for (int i = 1; i <= n; i++)
       for (int j = i; j <= n; j++)
        f[t|s[i][j]] = min(f[t|s[i][j]],f[t]+1);
    printf("%d\n",f[(1<<n)-1]);
}

int main() {
    //freopen("angrybirds.in","r",stdin);freopen("angrybirds.out","w",stdout);
    int T; read(T);
    while(T--) work();
    return 0;
}

这个题比较有趣 枚举+bfs+状压一下就能过 然而放在D2T3我觉得很厉害..
我们用结构体读入每个点 然后用n^2的时间来枚举这两个点（因为过原点已经除去了c）能否构成a<0的抛物线（circle函数） 若能 就将此抛物线经过的每个点加入这条线的状态 然后再加入f数组 因为有可能出现a<0的抛物线怎么都不能同时过两个点的情况 我们就将只过一个点的状态也加入f数组。然后跑bfs 记录达到此状态需要的最少鸟的个数 若跑到mx（所有猪都被打下来 也就是所有位数都为1）就break掉 保证最小步数。
注意细节部分 比如判断哪些点能在此抛物线上 以及eps应该开的尽量小一点
总耗时1068ms
峰值内存3.812 MiB
#1 Accepted 5ms 3.305 MiB
#2 Accepted 8ms 3.312 MiB
#3 Accepted 5ms 3.316 MiB
#4 Accepted 7ms 3.309 MiB
#5 Accepted 6ms 3.305 MiB
#6 Accepted 10ms 3.309 MiB
#7 Accepted 4ms 3.312 MiB
#8 Accepted 4ms 3.312 MiB
#9 Accepted 4ms 3.305 MiB
#10 Accepted 4ms 3.316 MiB
#11 Accepted 8ms 3.301 MiB
#12 Accepted 8ms 3.312 MiB
#13 Accepted 15ms 3.305 MiB
#14 Accepted 18ms 3.309 MiB
#15 Accepted 24ms 3.434 MiB
#16 Accepted 61ms 3.438 MiB
#17 Accepted 68ms 3.43 MiB
#18 Accepted 241ms 3.812 MiB
#19 Accepted 291ms 3.805 MiB
#20 Accepted 268ms 3.812 MiB
下面放代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
#define mod 1000000007
#define INF 0x3f3f3f3f
#define res(i,x,y) for(register int i=x;i<=y;++i)
#define resdown(i,x,y) for(register int i=x;i>=y;--i)
#define finout freopen(".in","r",stdin);freopen(".out","w",stdout);
using namespace std;
template <typename T> inline void read(T& x){
    x=0;char c;int s=1;
    do{c=getchar();if(c=='-')s=-1;}while(c>'9' or c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c<='9' and c>='0');x*=s;
}
struct node{
    double x,y;
}e[20];
queue<int>q;
int ans,vis[1<<18],f[1<<18],n,m,mx,cnt=0,step[1<<18];
inline void circle(double x1,double y1,double x2,double y2,int p1,int p2){
    double a=(x2*y1-y2*x1)/(x1*x1*x2-x1*x2*x2),b=(x1*x1*y2-x2*x2*y1)/(x1*x1*x2-x1*x2*x2);
    int cn=0;
    if(a>=0)return ;
    res(i,p2+1,n){
        if(abs(a*e[i].x*e[i].x+b*e[i].x-e[i].y)<= 1e-10)cn|=1<<(i-1);
    }
    cn|=(1<<(p1-1))|(1<<(p2-1));
    f[++cnt]=cn;
}
void bfs(){
    while(!q.empty())q.pop();
    memset(vis,0,sizeof vis);
    memset(step,0,sizeof step);
    res(i,1,cnt)vis[f[i]]=1,q.push(f[i]);
    int u,c;
    while(!q.empty()){
        u=q.front(),q.pop(),c=step[u]+1;
        if(u==mx){
            ans=c;break;
        }
        res(i,1,cnt){
            if(!vis[f[i]|u]){
                vis[f[i]|u]=1;
                step[f[i]|u]=c;
                q.push(f[i]|u);
            }
        }
    }
}
int main(){
//  finout
    int t;read(t);
    while(t--){
        read(n),read(m);
        ans=INF,cnt=0;
        mx=0;
        res(i,1,n)mx+=1<<(i-1);
        memset(e,0,sizeof e);
        memset(f,0,sizeof f);
        memset(vis,0,sizeof vis);
        res(i,1,n)
            scanf("%lf%lf",&e[i].x,&e[i].y);
        res(i,1,n){
            res(j,i+1,n){
                circle(e[i].x,e[i].y,e[j].x,e[j].y,i,j);
            }
            f[++cnt]=1<<(i-1);
        }
        bfs();
        cout<<ans<<endl;
    }
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int T,n,m;
int dp[524300],vis[20];
struct node{
    double x,y;
}a[20];
struct data{
    double c,d;
}l;
data work(double x,double y,double xx,double yy){
    l.c=(yy*x-y*xx)/(xx*xx*x-x*x*xx);
    l.d=(y-l.c*x*x)/x;
    return l;
}
bool check(double x,double y){
    if(abs(l.c*x*x+l.d*x-y)<0.000001) return true;
    return false;
}
int main(){
    //freopen("angrybirds.in","r",stdin);
    //freopen("angrybirds.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(dp,0x3f,sizeof(dp));
        dp[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%lf%lf",&a[i].x,&a[i].y);
            for(int j=0;j<=(1<<n)-1;j++){
                dp[j|(1<<(i-1))]=min(dp[j|(1<<(i-1))],dp[j]+1);
            }
        }
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            for(int j=i+1;j<=n;j++){
                if(vis[j]) continue;
                if(a[i].x==a[j].x) continue;
                work(a[i].x,a[i].y,a[j].x,a[j].y);
                if(l.c>=0.0) continue;
                int s=(1<<(i-1))|(1<<(j-1));
                for(int z=j+1;z<=n;z++)
                    if(check(a[z].x,a[z].y)) {vis[z]=1;s=s|(1<<(z-1));}
                for(int z=0;z<=(1<<n)-1;z++)
                    dp[z|s]=min(dp[z|s],dp[z]+1);
            }
        }
        printf("%d\n",dp[(1<<n)-1]);
    }
}

对于每两个点，尝试建立一条经过这两个点的抛物线（这条抛物线是唯一的），如果a<0，就加入到可用抛物线集合中。然后计算最少需要多少条抛物线。

#include <cstdio>
#include <algorithm>

using namespace std;

const double EPS = 1e-10;

const int INF = 2000000000;

int n, m;

int x[18];
int y[18];
int parabolas[400];
int possible[262144];

bool eql(double a, double b)
{
    if (a < b) {
        return b - a < EPS;
    } else {
        return a - b < EPS;
    }
}

int level(void)
{
    scanf("%d%d", &n, &m);
    (void)m;
    int p_cnt = 0;
    possible[0] = 0;
    for (int i = 1; i < (1 << n); i++) {
        possible[i] = INF;
    }
    for (int i = 0; i < n; i++) {
        int a, b, c, d;
        scanf("%d.%d %d.%d", &a, &b, &c, &d);
        x[i] = a*100+b;
        y[i] = c*100+d;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            double a, b;
            if (i == j) {
                parabolas[p_cnt++] = (1 << i);
                continue;
            }
            if (x[i] == x[j]) continue;
            a = ((double)(y[i]*x[j]-x[i]*y[j]))/((double)(x[i]*x[i]*x[j]-x[i]*x[j]*x[j]));
            b = ((double)(y[i]*x[j]*x[j]-x[i]*x[i]*y[j]))/((double)(x[i]*x[j]*x[j]-x[i]*x[i]*x[j]));
            if (a < -EPS) {
                int par = 0;
                for (int k = 0; k < n; k++) {
                    if (eql(a*x[k]*x[k]+b*x[k], y[k])) {
                        par += (1 << k);
                    }
                }
                parabolas[p_cnt++] = par;
            }
        }
    }
    for (int i = 0; i < p_cnt; i++) {
        for (int j = 0; j < (1 << n); j++) {
            possible[j | parabolas[i]] = min(possible[j] + 1, possible[j | parabolas[i]]);
        }
    }
    return possible[(1 << n) - 1];
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        printf("%d\n", level());
    }
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
const double eps=1e-10;

int n,m,T;
int f[(1<<18)];
int s[18+1][18+1];
double x[18+1];
double y[18+1];

int main()
{
    while (~scanf("%d",&T))
        for (int X=1;X<=T;X++)
        {
            scanf("%d%d",&n,&m);
            for (int i=1;i<=n;i++)
                scanf("%lf%lf",&x[i],&y[i]);
            memset(s,0,sizeof(s));
            for (int i=1;i<=n;i++)
                for (int j=i+1;j<=n;j++)
                    if (x[i]!=x[j]||y[i]==y[j])
                    {
                        double a_1=(y[j]*x[i]/x[j]-y[i])/(x[i]*x[j]-x[i]*x[i]);
                        double b_1=(y[i]-a_1*x[i]*x[i])/x[i];
                        if (a_1<-eps)
                        {
                            s[i][j]=((1<<(i-1))|(1<<(j-1)));
                            for (int k=1;k<=n;k++)
                                if (i!=k&&j!=k)
                                {
                                    double a_2=(y[k]*x[i]/x[k]-y[i])/(x[i]*x[k]-x[i]*x[i]);
                                    double b_2=(y[i]-a_1*x[i]*x[i])/x[i];
                                    s[i][j]|=((fabs(a_1-a_2)<eps&&fabs(b_1-b_2)<eps)?(1<<(k-1)):0);
                                }
                            s[j][i]=s[i][j];
                        }
                    }
            for (int i=1;i<=n;i++)
                s[i][i]|=(1<<(i-1));
            memset(f,oo_max,sizeof(f));
            f[0]=0;
            for (int x=0;x<(1<<n)-1;x++)
                for (int i=1;i<=n;i++)
                    for (int j=i;j<=n;j++)
                        f[x|s[i][j]]=min(f[x|s[i][j]],f[x]+1);
            printf("%d\n",f[(1<<n)-1]);
        }
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 100005

int n,m,d,num,now;
char s[N][20];
int len[N],dir[N],pre[N],nxt[N];

int main()
{
freopen("toy.in","r",stdin);
freopen("toy.out","w",stdout);
scanf("%d%d\n",&n,&m);
for (int i=1;i<=n;++i)
{
gets(s[i]);len[i]=strlen(s[i]);
dir[i]=s[i][0]-'0';
for (int j=1;j<len[i]-1;++j) s[i][j]=s[i][j+1];
}
/*
for (int i=1;i<=n;++i)
{
for (int j=1;j<=len[i]-2;++j) putchar(s[i][j]);
putchar('\n');
}
*/
now=1;
for (int i=1;i<=m;++i)
{
scanf("%d%d",&d,&num);
if (!d)//left
{
if (!dir[now])//in
{
now=((now-num-1)%n+n)%n+1;
}
else//out
{
now=(now+num-1)%n+1;
}
}
else//right
{
if (!dir[now])
{
now=(now+num-1)%n+1;
}
else
{
now=((now-num-1)%n+n)%n+1;
}
}
}
for (int i=1;i<=len[now]-2;++i)
putchar(s[now][i]);
putchar('\n');
}