记录编号	608777	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2561.[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.598 s
提交时间	2025-10-29 12:00:46	内存使用	3.89 MiB

#include<bits/stdc++.h>
#include<random>
using namespace std;

const double EPS = 1e-7;

double x[20], y[20];
int n, T, m;
vector<int> masks;
unordered_set<int> st;
mt19937 rng(time(NULL));

int rnd(int l, int r){
	return uniform_int_distribution<int>(l, r)(rng);
}

int Get(int i, int j){
	if(fabs(x[i] - x[j]) < EPS){
		return 0;
	}
	double x_1 = x[i], x_2 = x[j];
	double y_1 = y[i], y_2 = y[j];
	double a = (y_1 * x_2 - y_2 * x_1) / (x_1 * x_2 * (x_1 - x_2));
	if(a >= -EPS){
		return 0;
	}
	double b = y_1 / x_1 - a * x_1;
	int mask = 0;
	for(int k = 0;k < n;k ++){
		double cyc = a * x[k] * x[k] + b * x[k];
		if(fabs(cyc - y[k]) < EPS){
			mask |= (1 << k);
		}
	}
	return mask;
}

int SA(){
	masks.clear();
	st.clear();
	for(int i = 0;i < n;i ++){
		int mask = (1 << i);
		masks.push_back(mask);
		st.insert(mask);
	}
	for(int i = 0;i < n;i ++){
		for(int j = i + 1;j < n;j ++){
			int mask = Get(i, j);
			if(mask && !st.count(mask)){
				masks.push_back(mask);
				st.insert(mask);
			}
		}
	}

	int bk = (1 << n) - 1;
	int ans = n, cnt;
	vector<int> cur;

	int cov = 0;
	while(cov != bk){
		int bt = 0, nw = -1;
		for(int m : masks){
			int ncov = __builtin_popcount(m & ~cov);
			if(ncov > nw){
				nw = ncov;
				bt = m;
			}
		}
		cur.push_back(bt);
		cov |= bt;
	}
	cnt = cur.size();
	ans = min(ans, cnt);

	double temp = 50.0;
	double dec = 0.70;
	int p = 8 * n;
	while(temp > EPS){
		for(int k = 0;k < p;k ++){
			vector<int> nw_cur = cur;
			int op = rnd(0, 2);
			if(op == 0){
				if(nw_cur.empty() || masks.empty()) continue;
				int idx = rnd(0, nw_cur.size() - 1);
				int nm = masks[rnd(0, masks.size() - 1)];
				nw_cur[idx] = nm;
				int tot = 0;
				for(int m : nw_cur) tot |= m;
				if(tot == bk){
					int nc = nw_cur.size();
					if(nc < cnt || (double)rnd(0, RAND_MAX)/RAND_MAX < exp((cnt - nc)/temp)){
						cur = nw_cur;
						cnt = nc;
					}
				}
			}
			else if(op == 1){
				if(nw_cur.size() <= 1 || masks.empty()) continue;
				int idx = rnd(0, nw_cur.size() - 1);
				nw_cur.erase(nw_cur.begin() + idx);
				int c = 0;
				for(int m : nw_cur) c |= m;
				int bt = 0, mx = -1;
				for(int m : masks){
					int add = __builtin_popcount(m & ~c);
					if(add > mx) mx = add, bt = m;
				}
				if(mx <= 0) continue;
				nw_cur.push_back(bt);
				int tot = 0;
				for(int m : nw_cur) tot |= m;
				if(tot == bk){
					int nc = nw_cur.size();
					if(nc < cnt || (double)rnd(0, RAND_MAX)/RAND_MAX < exp((cnt - nc)/temp)){
						cur = nw_cur;
						cnt = nc;
					}
				}
			}
			else{
				if(nw_cur.size() < 2) continue;
				int i = rnd(0, nw_cur.size() - 1);
				int j = rnd(0, nw_cur.size() - 1);
				if(i == j) continue;
				if(i > j) swap(i, j);
				int comb = nw_cur[i] | nw_cur[j];
				if(!st.count(comb)) continue;
				nw_cur.erase(nw_cur.begin() + j);
				nw_cur.erase(nw_cur.begin() + i);
				nw_cur.push_back(comb);
				int nc = nw_cur.size();
				if(nc < cnt || (double)rnd(0, RAND_MAX)/RAND_MAX < exp((cnt - nc)/temp)){
					cur = nw_cur;
					cnt = nc;
				}
			}
			ans = min(ans, cnt);
		}
		temp *= dec;
	}
	return ans;
}


int main(){
	freopen("angrybirds.in", "r", stdin);
	freopen("angrybirds.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	while(T --){
		cin >> n >> m;
		for(int i = 0;i < n;i ++){
			cin >> x[i] >> y[i];
		}
		cout << SA() << '\n';
	}
	return 0;
}