记录编号	357315	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]愤怒的小鸟	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	0.068 s
提交时间	2016-12-10 15:47:14	内存使用	4.29 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>

#define allset(x) ((1<<x)-1)

using namespace std;

#define EPS 1e-8
inline double abs(double x) {
    return x < 0 ? -x : x;
}

#define eqdouble(x,y) (abs(x-y) <= EPS)
#define lessthan(x,y) (x+EPS<y)
#define throwline(a,b,x) (a*x*x+b*x)
#define pigid(x) (1<<x)

int minV, N, M;
double pigx[18], pigy[18];

struct _set {
	int x;
	int num;
	inline bool operator<(const _set& rhs) const {
		return num > rhs.num;
	}
} sets[400];

int Nset;

void solve(double &a, double &b, double x1, double y1, double x2, double y2) {
    double x12 = x1*x1, x22 = x2*x2, 
        kc0 = y1+y2, ka0 = x12+x22, kb0 = x1+x2,
        kc1 = y1-y2, ka1 = x12-x22, kb1 = x1-x2,
        kb1divkb0;
    if(kb0 == 0) return;
    kb1divkb0 = kb1 / kb0;
    if(ka0*kb1divkb0-ka1 == 0) return;
    a = (kc0*kb1divkb0-kc1)/(ka0*kb1divkb0-ka1);
    b = (kc0-ka0*a)/kb0;
}

int queue[262144], qH, qT, dep[262144], left[262144];
int vis[262144], visid = 0;

int main() {
    freopen("angrybirds.in", "rt", stdin);
    freopen("angrybirds.out", "wt", stdout);

    int i,T,k,t,num;
    double a,b;
    
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &N, &M);
        for(i=0;i<N;i++) {
            scanf("%lf%lf", &pigx[i], &pigy[i]);
        }

        //pre-process
        Nset = 0;
        visid++; //clear vis
        for(i=0;i<N;i++) {
            for(k=i+1;k<N;k++) {
                a=0; solve(a,b,pigx[i],pigy[i],pigx[k],pigy[k]);
                if(lessthan(a,0)) {
                    sets[Nset].x = pigid(i) | pigid(k);
                    num = 2;
                    for(t=0;t<N;t++) {
                        if(t!=i && t!=k && eqdouble( throwline(a,b,pigx[t]), pigy[t] )) {
                            sets[Nset].x |= pigid(t); num++;
                        }
                    }
                    if(vis[sets[Nset].x] != visid) {
                    	vis[sets[Nset].x] = visid;
                    	sets[Nset].num = num;
                    	Nset++;
					}
                }
            }
        }

		sort(sets, sets+Nset);

        //node sorting
        visid++; //clear vis

        qH = 0; qT = 1;
        queue[0] = allset(N);
        dep[0] = 0;
        left[0] = N;
        minV = N;

        int U, cdep, cleft;
        while(qH < qT) {
        	U = queue[qH]; cdep = dep[qH]; cleft = left[qH]; qH++;

        	if(U == 0) {
        		minV = cdep;
        		break;
			}
			if(cleft+cdep < minV) {
				minV = cleft+cdep;
			}
        	for(i=0;i<Nset;i++) {
        		t = U & (~sets[i].x);
        		if(vis[t] != visid) {
        			vis[t] = visid;
        			
        			num = 0;
        			for(k=0;k<N;k++) {
        				if(t & pigid(k)) num++;
					}
        			queue[qT] = t;
        			dep[qT] = cdep+1;
        			left[qT] = num;
        			qT++;
				}
			}
		}

        printf("%d\n", minV);
    }
}