$$\color{Red}{愤怒的小鸟 步骤详解}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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

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

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

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

在游戏的某个关卡里，平面的第一象限中有n 只绿色的小猪，其中第i
只小猪所在的坐标为(xi,yi)

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

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

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

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

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

这些指令将在输入格式中详述。

假设这款游戏一共有T个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。

由于她不会算，所以希望由你告诉她。

注意:本题除 NOIP 原数据外，还包含加强数据。

输入格式

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

下面依次输入这 T 个关卡的信息。

每个关卡第一行包含两个非负整数 n,m，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。

接下来的 n 行中，第 i 行包含两个正实数 (xi,yi)，表示第 i 只小猪坐标为 (xi,yi)，数据保证同一个关卡中不存在两只坐标完全相同的小猪。

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

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

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

保证 1≤n≤18，0≤m≤2，0<xi,yi<10，输入中的实数均保留到小数点后两位。

上文中，符号 ⌈c⌉ 和 ⌊c⌋ 分别表示对 c 向上取整和向下取整，例如：⌈2.1⌉=⌈2.9⌉=⌈3.0⌉=⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。H)，中间没有空格。按顺序表示地图中每一行的数据。

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

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

数据范围

1≤n≤18，0≤m≤2，0<xi,yi<10

输入样例：

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

输出样例：

1
1

思考

从最暴力的角度去看这道题

首先这道题是融合了初中的抛物线知识点，这里显然，对于一个一元二次方程 ax^2 + bx + c而言，抛物线是必过(0, 0)点且开口向下的，即c == 0,a < 0;

那么我们可以枚举两两结合的点，先存储他们构成的抛物线，除了他们两个还能覆盖哪些别的点，当然需要满足首先这两个点能构成抛物线，因为需要满足过零点，可能y太小的点无法和其他的点构成抛物线，同时x相同的点，即同一纵轴的点一定无法构成抛物线，我们使用一个数组path[i][j]来存储它

那么我们的动态规划就可以这么来看f[i]---> 可以把当前状态为i 的猪都打死所需要的 最小抛物线数量

然后我们可以从最暴力的角度，枚举所有可能的选择点的状态，然后找寻这个状态的一个0，也就是没有被打死的猪，假设它下标为x然后找寻所有能和它组成抛物线的情况，还能覆盖其他猪的情况path[x][j], 在这种情况下能打死猪的状态叠加之前枚举的状态，即f[i | path[x][j]] ，这个状态下最小的抛物线数量就是Min(f[i | path[x][j]], f[i] + 1)，即不选这个抛物线的原始值，或者是在i状态的基础上，选择path[x][j]的情况

其实会有人说，这样真的是最优解吗？
因为我们枚举的这个path[x][j]，也许最优解的情况下，并不是x和j构成的抛物线打死的他们两个中的一个，这么枚举少了很多种情况，其实，path[x][j] 是以点(x, j)构成的抛物线，保证了x 一定被覆盖。那么也可能存在path[a][b]也能覆盖 x点，在我们确定点x，枚举 j 的过程中一定可以将所有穿过 x 点的抛物线枚举到，即path[a][b]所构成的抛物线方程是和path[x][j]其中一个是完全等价的，则存的状态也是一样的，故全体方案都可以被枚举到。

这道题还需要注意的是，我们使用的是double类型，判断是否相等不能使用==，而需要自己单独写一个方法

    static boolean cmp(double x, double y) {
        return Math.abs(x - y) < 0.000001;
    }

以及如何根据两个点确定一个抛物线？

已知两个点——》(x1, y1) (x2, y2)

构成两个抛物线方程：ax1^2 + bx1 = y1     ax2^2 + bx2 = y2

然后我们算a和b的值即可确定这条抛物线

两式联立先消除b，即能计算出a的值: ax1 - ax2 = y1/x1 - y2/x2  = >  a = (y1/ x1 - y2/x2) / (x1 - x2)

然后随便选一个式子代入a的值，即可算出b: b = (y1 - ax1^2) / x1

JAVA代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static class PDD {
        public double x, y;

        public PDD(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }

    static int N = 20, M = 1 << 18;
    static int[] f = new int[M];
    static int[][] path = new int[N][N];
    static PDD[] q = new PDD[N];
    static int n, m, T;

    static boolean cmp(double x, double y) {
        return Math.abs(x - y) < (double) 1e-8;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            String[] s1 = br.readLine().split(" ");
            n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);
            for (int i = 0; i < n; i++) {
                String[] s2 = br.readLine().split(" ");
                double x = Double.parseDouble(s2[0]);
                double y = Double.parseDouble(s2[1]);
                q[i] = new PDD(x, y);
                //把上一个T的path初始化为0
                Arrays.fill(path[i], 0);
            }
            //path数组存放每两个点构成的抛物线能覆盖到的点的二进制状态
            for (int i = 0; i < n; i++) {
                path[i][i] = 1 << i;
                for (int j = 0; j < n; j++) {
                    double x1 = q[i].x, y1 = q[i].y;
                    double x2 = q[j].x, y2 = q[j].y;
                    if (cmp(x1, x2)) continue;
                    //计算a 和 b 的值以确定抛物线
                    double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                    double b = (y1 - a * x1 * x1) / x1;
                    //把开口向上的排除
                    if (a > 0 || cmp(a, 0)) continue;
                    for (int k = 0; k < n; k++) {
                        double x3 = q[k].x, y3 = q[k].y;
                        if (cmp((a * x3 * x3 + b * x3), y3)) path[i][j] += 1 << k;
                    }
                }
            }
            //存放最小值，需要进行状态方程初始化无穷大
            //且起点赋值为0,状态0即目前所有的小猪都存活，即没有抛物线存在
            Arrays.fill(f, 0x3f3f3f3f);
            f[0] = 0;

            for (int i = 0; i < 1 << n; i++) {
                int x = 0;
                //找寻第一个存活的小猪
                for (int j = 0; j < n; j++) {
                    if ((i >> j & 1) == 0) {
                        x = j;
                        break;
                    }
                }
                for (int j = 0; j < n; j++) {
                    f[i | path[x][j]] = Math.min(f[i | path[x][j]], f[i] + 1);
                }
            }
            System.out.println(f[(1 << n) - 1]);
        }
    }
}