题目链接

题目描述

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

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

有一架弹弓位于 $(0,0)$ 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 $y=ax^2+bx$ 的曲线，其中 $a,b$ 是 Kiana 指定的参数，且必须满足 $a < 0$，$a,b$ 都是实数。

当小鸟落回地面（即 $x$ 轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有 $n$ 只绿色的小猪，其中第 $i$ 只小猪所在的坐标为 $\left(x_i,y_i \right)$。

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

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

例如，若两只小猪分别位于 $(1,3)$ 和 $(3,3)$，Kiana 可以选择发射一只飞行轨迹为 $y=-x^2+4x$ 的小鸟，这样两只小猪就会被这只小鸟一起消灭。

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

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

假设这款游戏一共有 $T$ 个关卡，现在 Kiana想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。

输入格式

第一行包含一个正整数 $T$，表示游戏的关卡总数。

下面依次输入这 $T$ 个关卡的信息。每个关卡第一行包含两个非负整数 $n,m$，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 $n$ 行中，第 $i$ 行包含两个正实数 $x_i,y_i$，表示第 $i$ 只小猪坐标为 $(x_i,y_i)$。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果 $m=0$，表示 Kiana 输入了一个没有任何作用的指令。

如果 $m=1$，则这个关卡将会满足：至多用 $\lceil n/3 + 1 \rceil$ 只小鸟即可消灭所有小猪。

如果 $m=2$，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 $\lfloor n/3 \rfloor$ 只小猪。

保证 $1\leq n \leq 18$，$0\leq m \leq 2$，$0 < x_i,y_i < 10$，输入中的实数均保留到小数点后两位。

上文中，符号 $\lceil c \rceil$ 和 $\lfloor c \rfloor$ 分别表示对 $c$ 向上取整和向下取整，例如：$\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。

输出格式

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

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

题解

这是一道十足的搜索好题，可以用于练习 bfs。

首先做简单的数学推导，推出经过 $(x_1,y_1)$，$(x_2,y_2)$ 的抛物线

$$f(x_1) = y_1 = ax_1^2 + bx_1 \\ f(x_2) = y_2 = ax_2^2 + bx_2 \\ a = \dfrac{y_1 - bx_1}{x_1^2} = \dfrac{y_2 - bx_2}{x_2^2} \\ b = \dfrac{x_2^2y_1 - x_1^2y_1}{x_1x_2(x_2 - x_1)}$$

用二进制表示第 $i$ 个猪是否被打到（状态压缩）

每次通过极角序排序每个点，作为枚举顺序，最后 $\mathcal{O}(2^n)$ 枚举 $\mathcal{O}(n^2)$ 查询，最终时间复杂度 $\mathcal{O}(2^nn^2)$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 18;
const int MAXP = (1 << MAXN) + 20;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
struct Point {
    db x, y;
    Point(db _x = 0, db _y = 0) : x(_x), y(_y) {}
    bool operator<(const Point &rhs) const { return y * rhs.x < rhs.y * x; }
};
int n, m, _;
int d[MAXP];
Point pigs[MAXN];
inline void solve(db &a, db &b, db x1, db y1, db x2, db y2) {
    b = (y1 * x2 * x2 - y2 * x1 * x1) / x1 / x2 / (x2 - x1);
    a = (y1 - b * x1) / x1 / x1;
}
int q[MAXP], qhead = 0, qtail = 0;
// bfs 加入新的状态
inline void extend(int u, int v) {
    if (d[v] == INF) {
        d[v] = d[u] + 1;
        q[qtail++] = v;
    }
}
inline int bfs(int s) {
    d[s] = 0;
    qhead = qtail = 0;
    q[qtail++] = s;
    while (qhead != qtail) {
        int now = q[qhead++];
        if (now == (1 << n) - 1)
            return d[now];
        int p0 = 0;  // 当前第一只没有被打到的猪
        for (int t = now; t & 1; t >>= 1) p0++;
        extend(now, now | (1 << p0));
        for (int i = p0 + 1; i < n; i++) {
            db a, b;
            // 极角排序后不能打出向上的曲线
            if (pigs[i].x + 0.0001 > pigs[p0].x)
                continue;
            // 也不能是一条直线
            if (fabs(pigs[i].x / pigs[i].y - pigs[p0].x / pigs[p0].y) < eps)
                continue;
            solve(a, b, pigs[p0].x, pigs[p0].y, pigs[i].x, pigs[i].y);
            // p0 和 i 代表的猪我们都打到了
            int to = now | (1 << p0) | (1 << i);
            // 找一找有没有恰好也被我们打到的猪
            for (int j = i + 1; j < n; j++) {
                db delta = fabs(a * pigs[j].x * pigs[j].x + b * pigs[j].x - pigs[j].y);
                if (delta < eps) {
                    to |= 1 << j;
                }
            }
            extend(now, to);
        }
    }
}
int main() {
    for (scanf("%d", &_); _; _--) {
        scanf("%d%d", &n, &m);
        memset(d, 0x3f, sizeof(d));
        for (int i = 0; i < n; i++) {
            db x, y;
            scanf("%lf%lf", &x, &y);
            pigs[i] = Point(x, y);
        }
        sort(pigs, pigs + n);
        printf("%d\n", bfs(0));
    }
    return 0;
}

注意

1. 抛物线不能是上凸的
2. 抛物线不能是一条直线

3. 要检查是否有本身不准备打但是最后经过了的猪

4. 多组数据要清空