记录编号	355269	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	3.970 s
提交时间	2016-11-24 10:34:08	内存使用	8.32 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const double eps = 1e-13;
#define fix(tar) (fabs(tar) < eps ? 0 : tar)

double posx[20], posy[20];

int n, type;

inline void read() {
	scanf("%d %d", &n, &type);
	for (int i = 1; i <= n; i++) {
		scanf("%lf %lf", &posx[i], &posy[i]);
	}
}

inline void cal(int i, int j, double &a, double &b) {
	double va1 = posx[i] * posx[i], va2 = posx[j] * posx[j];
	double vb1 = posx[i], vb2 = posx[j];
	double vc1 = posy[i], vc2 = posy[j];
	double t_va2 = va2 * vb1 / vb2;
	double t_vc2 = vc2 * vb1 / vb2;
	if (fix(va1 - t_va2) == 0) {
		a = 0, b = 0;
		return;
	}
	a = (vc1 - t_vc2) / (va1 - t_va2);
	b = (vc1 - va1 * a) / vb1;
}

inline bool judge(int k, double a, double b) {
	return fix(posy[k] - posx[k] * posx[k] * a - posx[k] * b) == 0;
}

namespace XTT {
	int f[1 << 21];
	int is_ok[32][32];
	
	inline void init() {
		for (int i = 1; i <= 20; i++) {
			for (int j = 1; j <= 20; j++) is_ok[i][j] = 0;
		}
		memset(f, 127, sizeof(f));
	}
	
	inline void solve() {
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				int now_statu = (1 << (i - 1)) | (1 << (j - 1));
				double a, b;
				cal(i, j, a, b);
				if (fix(a) >= 0) continue;
				if (fix(b) == 0) continue; 
				for (int k = j + 1; k <= n; k++) {
					if (judge(k, a, b)) now_statu |= (1 << (k - 1));
				}
				is_ok[i][j] = now_statu;
			}
		}

		int top = (1 << n) - 1;		
		for (int i = 0; i <= top; i++) {
			int tmp = i, cnt = 0;
			while (tmp) {
				if (tmp & 1) cnt++;
				tmp >>= 1;
			}
			f[i] = cnt;
		}
		
		for (int i = 0; i <= top; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = j + 1; k <= n; k++) {
					f[is_ok[j][k] | i] = min(f[is_ok[j][k] | i], f[i] + 1);
				}
			}
		}
		printf("%d\n", f[top]);
	}
}

int main() {
	freopen("angrybirds.in", "r", stdin);
	freopen("angrybirds.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while (T--) {
		read();
		XTT :: init();
		XTT :: solve();
	}
	return 0;
}