愤怒的小鸟（爆搜，剪枝）

题目描述

Kiana 最近沉迷于一款神奇的游戏无法自拔。

简单来说，这款游戏是在一个平面上进行的。

有一架弹弓位于 $y=ax^2+bxy=ax2+bx 的曲线，其中 a,ba,b 是Kiana 指定的参数，且必须满足 a < 0a<0 ， a,ba,b 都是实数。$

当小鸟落回地面（即

在游戏的某个关卡里，平面的第一象限中有 $left(x_i,y_i ight)(xi,yi) 。$

如果某只小鸟的飞行轨迹经过了 $x_i, y_i ight)(xi,yi) ，那么第 ii 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；$

如果一只小鸟的飞行轨迹没有经过 $x_i, y_i ight)(xi,yi) ，那么这只小鸟飞行的全过程就不会对第 ii 只小猪产生任何影响。$

例如，若两只小猪分别位于 $y=-x^2+4xy=−x2+4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。$

而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 Kiana来说都很难，所以Kiana还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

假设这款游戏一共有

输入输出格式

输入格式：

第一行包含一个正整数

下面依次输入这 $x_i,y_ixi,yi ，表示第 ii 只小猪坐标为 (x_i,y_i)(xi,yi) 。数据保证同一个关卡中不存在两只坐标完全相同的小猪。$

如果

保证 $x_i,y_i < 100<xi,yi<10 ，输入中的实数均保留到小数点后两位。$

上文中，符号

输出格式：

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。

思路：

没什么好说的。。。只能%%一群状压大佬

我是这么想的，一个猪被打掉，要么是单独的一只小鸟干的

要么是被一只路过的小鸟干的

那么，在经过一个没有被打掉的猪的时候，将这个猪与其他没有打掉的猪尝试配对

算出一条抛物线，看这条路上能打掉几只猪，并打标记

当然，也可以不算抛物线，默认用一只鸟打掉

加一个最优化剪枝即可

（ps 注意精度）

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define rii register int i
#define rij register int j
#define inf 19260817
#define eps 0.0000001
using namespace std;
int n,m,t,ans;
struct pw{
    double a,b;
}pwx[20];
struct pig{
    double x,y;
}zb[20];
double bjx[20],bjy[20];
inline pw echs(int wz,int i)
{
    pw an;
    double lzn=zb[wz].x;
    double rxz=zb[wz].y;
    double ltt=(rxz*bjx[i]-bjy[i]*lzn);
    ltt/=(lzn*lzn*bjx[i]-bjx[i]*bjx[i]*lzn);
    double kkk=(rxz-lzn*lzn*ltt)/lzn;
    an.a=ltt;
    an.b=kkk;
    return an;
}
void dfs(int wz,int sl,int sy)
{
    if(sl+sy>=ans)
    {
        return;
    }
    if(wz>=n+1)
    {
        ans=sl+sy;
        return;
    }
    int pd=0;
    for(rii=1;i<=sl;i++)
    {
        if(fabs(pwx[i].a*zb[wz].x*zb[wz].x+pwx[i].b*zb[wz].x-zb[wz].y)<=eps)
        {
            dfs(wz+1,sl,sy);
            pd=1;
            break;
        }
    }
    if(pd!=1)
    {
        for(rii=1;i<=sy;i++)
        {
            if(fabs(zb[wz].x-bjx[i])<eps)
            {
                continue;
            }
            pw kk=echs(wz,i);
            if(kk.a<0)
            {   
                pwx[sl+1]=kk;
                double ltt=bjx[i];
                double kkk=bjy[i];
                for(rij=i;j<sy;j++)
                {
                    bjx[j]=bjx[j+1];
                    bjy[j]=bjy[j+1];
                }
                dfs(wz+1,sl+1,sy-1);
                for(rij=sy;j>i;j--) 
                {
                    bjx[j]=bjx[j-1];
                    bjy[j]=bjy[j-1];
                }
                bjx[i]=ltt;
                bjy[i]=kkk;
            }
        }
        bjx[sy+1]=zb[wz].x;
        bjy[sy+1]=zb[wz].y;
        dfs(wz+1,sl,sy+1);
    }
}
int main()
{
    scanf("%d",&t);
    for(rii=1;i<=t;i++)
    {
        scanf("%d%d",&n,&m);
        for(rij=1;j<=n;j++)
        {
            scanf("%lf%lf",&zb[j].x,&zb[j].y);
        }
        ans=inf;
        dfs(1,0,0);
        printf("%d
",ans); 
    } 
}