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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

#define MAXN (20)
#define CY (1e-8)
#define INF (0x7fffffff)

inline void cal(int i, int j, double &a, double &b);
inline void process(void);
inline void solve(void);

double x[MAXN], y[MAXN];
int dp[1 << MAXN], ss[MAXN][MAXN];
int N, M, CaseNum;

int main() { 
#ifndef LOCAL
    freopen("angrybirds.in", "r", stdin);
    freopen("angrybirds.out", "w", stdout);
#endif
    scanf("%d", &CaseNum);
    while(CaseNum--) { 
        memset(ss, 0x00, sizeof(ss));
        memset(dp, 0x3f, sizeof(dp));
        scanf("%d%d", &N, &M);
        for(int i = 0; i < N; ++i) 
            scanf("%lf%lf", x + i, y + i);
        process();
        solve();
        printf("%d\n", dp[(1 << N) - 1]);
    }
    return 0;
}

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

inline void solve(void) { 
    dp[0] = 0;
    for(int i = 0; i < (1 << N); ++i) { 
        int k = __builtin_ctz(~i);
        dp[i | (1 << k)] = min(dp[i | (1 << k)], dp[i] + 1);
        for(int j = k + 1; j < N; ++j) 
            dp[i | ss[k][j]] = min(dp[i | ss[k][j]], dp[i] + 1);
    }
}

inline char dcmp(double a, double b) { 
    return abs(a - b) < CY ? 0 : (a < b ? -1 : 1);
}

inline void process(void) { 
    register 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)) continue;
            for(int k = 0; k < N; ++k) 
                if(!dcmp(a*x[k]*x[k] + b*x[k], y[k])) 
                    ss[i][j] |= (1 << k);
        }
    return ;
}