noip2016 洛谷 P2831 愤怒的小鸟

题目：愤怒的小鸟

思路：
搜索。
对于每一只鸟，如果可以被之前的抛物线经过，就可以合并，不需要考虑。
否则就先考虑能否和之前的单个点组成抛物线，或者单独成一个点。
要先考虑第一种情况以便于进行最优性剪枝。
一定要注意精度问题！！！WA了好多遍！！！
判断两个double类型相等：

bool issame(db x,db y) {
    if(fabs(x-y)<1e-8) return true;else return false;
}

代码：

#include<bits/stdc++.h>
using namespace std;#define maxn 20
#define read(x) scanf("%d",&x)
#define db double
#define readdb(x) scanf("%lf",&x)struct Pig{
    db x,y;Pig(){
    }Pig(db xx,db yy) {
    x=xx,y=yy;}
};struct Pair{
    db x,y;Pair(){
    }Pair(db xx,db yy) {
    x=xx,y=yy;}
};int n,m;
Pig pig[maxn+5];bool single[maxn+5];
vector<Pair> hv; int ans=1e9;
int sg=0;bool judge(Pig x,Pig y) {
    db x1=x.x,y1=x.y/x1;db x2=y.x,y2=y.y/x2;if(x1==x2||y1==y2) return false;db a=(y1-y2)/(x1-x2);db b=y1-a*x1;if(a>=0) return false ;return true;
}Pair find(Pig x,Pig y) {
    db x1=x.x,y1=x.y/x1;db x2=y.x,y2=y.y/x2;db a=(y1-y2)/(x1-x2);db b=y1-a*x1;return Pair(a,b);
}bool issame(db x,db y) {
    if(fabs(x-y)<1e-8) return true;else return false;
}void dfs(int x) {
    if(sg+hv.size()>=ans) return ;if(x==n+1) {
    ans=min(ans,(int)hv.size()+sg);return ;}for(int i=0;i<hv.size();i++) {
    if(issame(pig[x].x*pig[x].x*hv[i].x+pig[x].x*hv[i].y,pig[x].y)) {
    dfs(x+1);return ;}}for(int i=1;i<x;i++) {
    if(!single[i]) continue;if(judge(pig[i],pig[x])) {
    single[i]=0;sg--;hv.push_back(find(pig[i],pig[x]));dfs(x+1);hv.pop_back();sg++;single[i]=1;}}single[x]=true;sg++;dfs(x+1);sg--;single[x]=false;
}int main() {
    int T;read(T);while(T--) {
    ans=1e9;read(n),read(m);for(int i=1;i<=n;i++) {
    readdb(pig[i].x),readdb(pig[i].y);}dfs(1);printf("%d\n",ans);}return 0;
}