记录编号	608804	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2561.[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	梦那边的美好TT	是否通过	通过
代码语言	C++	运行时间	0.682 s
提交时间	2025-10-29 15:03:51	内存使用	4.00 MiB

#include <bits/stdc++.h>
#define N 19
using namespace std;

int t, n, dp[1<<N];
vector<int> masks;
struct node {
	double x, y;
} a[N];

bool cmp(node a, node b) {
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}

inline bool eq(double a, double b) {
	return fabs(a - b) < 1e-10;
}

int main() {
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;

	while (t--) {
		int mm;
		cin >> n >> mm;
		masks.clear();
		for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
		sort(a, a + n, cmp);

		set<pair<double, double>> seen;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				double x1 = a[i].x, y1 = a[i].y, x2 = a[j].x, y2 = a[j].y;
				if (eq(x1, x2)) continue;

				double denom = x1 * x2 * (x1 - x2);
				double k1 = (y1 * x2 - y2 * x1) / denom;
				double k2 = (y1 / x1) - k1 * x1;

				if (k1 > 1e-10 || eq(k1, 0)) continue;
				if (seen.count({k1, k2})) continue;
				seen.insert({k1, k2});

				int mask = 0;
				for (int k = 0; k < n; k++) {
					double val = k1 * a[k].x * a[k].x + k2 * a[k].x;
					if (eq(val, a[k].y)) mask |= 1 << k;
				}
				masks.push_back(mask);
			}
		}

		for (int i = 0; i < n; i++) masks.push_back(1 << i);

		fill(dp, dp + (1<<n), 0x3f);
		dp[0] = 0;
		int full = (1<<n) - 1;
		for (int i = 0; i < (1<<n); i++) {
			if (dp[i] == 0x3f) continue;
			for (int m : masks) {
				int nxt = i | m;
				if (dp[nxt] > dp[i] + 1) dp[nxt] = dp[i] + 1;
				if (nxt == full) break;
			}
		}

		cout << dp[full] << '\n';
	}
	return 0;
}