题解

「愤怒的小鸟」要用尽量少的抛物线把所有的猪覆盖。
每条抛物线形如：

并要求 $a < 0$（弹道必须向下开口）。思路是回溯枚举：

1. 按输入顺序逐个处理点。数组 $A[i]$、$B[i]$ 记录点 $i$ 所在抛物线的系数，$0$ 表示尚未分配。
2. 对当前点，若前面已存在抛物线且它能满足$$a x_i^2 + b x_i = y_i$$ 则直接沿用该抛物线。
3. 否则尝试与以前尚未建线的点两两配对。由两点坐标可以解出唯一的 $a,b$，只有当 $a < 0$ 时才是合法轨迹。临时把这两点分配到新抛物线并继续递归。
4. 如果以上都不行，则把当前点单独留到后面（表示“这个点还没打”），继续递归。
   $sum$ 统计当前已经新建的抛物线数量，若 $sum \ge ans$（当前最优）就剪枝。

搜索结束时的最小 $ans$ 即为答案。由于 $n \le 18$，回溯结合剪枝就能通过。

#include<bits/stdc++.h>
using namespace std;
int n, ans;
double A[20], B[20], X[20], Y[20];
bool eq(double a, double b)
{
	return abs(a - b) < 1e-8;
}
void dfs(int id, int s)
{
	int sum = s;
	for (int i = 1;i < id;i++)
	{
		if (eq(A[i], 0))
		{
			sum++;
		}
	}
	if (sum >= ans)
	{
		return;
	}
	if (id > n)
	{
		ans = sum;
		return;
	}
	for (int i = 1;i < id;i++)
	{
		if (!eq(A[i], 0.0) && eq(A[i] * X[id] * X[id] + B[i] * X[id], Y[id]))
		{
			A[id] = A[i];
			B[id] = B[i];
			dfs(id + 1, s);
			return;
		}
		if (A[i] == 0.0)
		{
			double d = X[i] * X[id] * (X[i] - X[id]);
			if (!eq(d, 0))
			{
				double k1 = (X[id] * Y[i] - X[i] * Y[id]) / d, k2 = (X[i] * X[i] * Y[id] - X[id] * X[id] * Y[i]) / d;
				if (k1 < 0)
				{
					A[i] = A[id] = k1;
					B[i] = B[id] = k2;
					dfs(id + 1, s + 1);
					A[i] = B[i] = 0.0;
 				}
			}
		}
	}
	A[id] = B[id] = 0.0;
	dfs(id + 1, s);
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int u;
		cin >> n >> u;
		memset(A, 0, sizeof(A));
		memset(B, 0, sizeof(B));
		memset(X, 0, sizeof(X));
		memset(Y, 0, sizeof(Y));
		for (int i = 1;i <= n;i++)
		{
			cin >> X[i] >> Y[i];
		}
		ans = 1e9;
		dfs(1, 0);
		cout << ans << endl;
	}
}