记录编号	444957	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.395 s
提交时间	2017-09-04 19:36:19	内存使用	1.31 MiB

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

const int MAXN = 18, INF = 0x3f3f3f3f;

int n, m, dp[1 << MAXN], ss[MAXN][MAXN];
double x[MAXN], y[MAXN];

inline void cal(int i, int j, double &a, double &b) {
    a = (y[i] - y[j] * (x[i] / x[j])) / (x[i] * x[i] - x[i] * x[j]);
    b = (y[i] - a * x[i] * x[i]) / x[i];
}

inline int dcmp(const double &a, const double &b) {
    return fabs(a - b) < 1e-8 ? 0 : (a < b ? -1 : 1); 
}

void process() {
    double a, b;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j < n; ++j) {
            cal(i, j, a, b);
            if(dcmp(a, 0) != -1) { // a >= 0
                ss[i][j] = (1 << n) - 1; // ss[i][j] = 111...111;
                continue;
            }
            ss[i][j] = 0; // a < 0
            for(int k = 0; k < n; ++k) {
                if(dcmp(a * x[k] * x[k] + b * x[k], y[k]) != 0) { // a, b can't shoot the pig k
                    ss[i][j] |= (1 << k);
                }
            }
        }

    }
}

inline void tension(int &a, const int &b) { if (b < a) a = b; } // a = min(a, b);

void solve() {
    dp[0] = 0;
    for(register int s = 1, i, j; s < (1 << n); ++s) {
        dp[s] = INF;
        i = __builtin_ctz(s); // __builtin_ctz(10011000) = 3  the place of first 1 - 1
        tension(dp[s], dp[s ^ (1 << i)] + 1);
        for(j = i + 1; j < n; ++j) {
            if((s >> j) & 1) 
                tension(dp[s], dp[s & ss[i][j]] + 1);
        }
    }
    printf("%d\n", dp[(1 << n) - 1]);
}

int main() { 
#ifndef LOCAL
    freopen("angrybirds.in", "r", stdin);
    freopen("angrybirds.out", "w", stdout);
#endif
    int casenum;
    scanf("%d", &casenum);
    for(int t = 0; t < casenum; ++t) {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i) {
            scanf("%lf%lf", x + i, y + i);
        }
        process();
        solve();
    }
}