【NOIP2016】憤怒的小鳥

題目描述

Kiana最近沉迷于一款神奇的游戲無法自拔。

簡單來說，這款游戲是在一個平面上進行的。

有一架彈弓位于(0,0)處，每次Kiana可以用它向第一象限發射一只紅色的小鳥，小鳥們的飛行軌跡均為形如的曲線，其中a,b是Kiana指定的參數，且必須滿足a<0。

當小鳥落回地面(即x軸）時，它就會瞬間消失。

在游戲的某個關卡里，平面的第一象限中有n只綠色的小豬，其中第i只小豬所在的坐標為(xi,yi)。

如果某只小鳥的飛行軌跡經過了(xi,yi),那么第i只小豬就會被消滅掉，同時小鳥將會沿著原先的軌跡繼續飛行；

如果一只小鳥的飛行軌跡沒有經過(xi,yi)，那么這只小鳥飛行的全過程就不會對第i只小豬產生任何影響。

例如，若兩只小豬分別位于(1,3)和(3,3)，Kiana可以選擇發射一只飛行軌跡為的小鳥，這樣兩只小豬就會被這只小鳥一起消滅。

而這個游戲的目的，就是通過發射小鳥消滅所有的小豬。

這款神奇游戲的每個關卡對Kiana來說都很難，所以Kiana還輸入了一些神秘的指令，使得自己能更輕松地完成這個游戲。這些指令將在【輸入格式】中詳述。

假設這款游戲一共有T個關卡，現在Kiana想知道，對于每一個關卡，至少需要發射多少只小鳥才能消滅所有的小豬。由于她不會算，所以希望由你告訴她。

輸入輸出格式

輸入格式：

?

第一行包含一個正整數T，表示游戲的關卡總數。

下面依次輸入這T個關卡的信息。每個關卡第一行包含兩個非負整數n,m，分別表示該關卡中的小豬數量和Kiana輸入的神秘指令類型。接下來的n行中，第i行包含兩個正實數(xi,yi)，表示第i只小豬坐標為(xi,yi)。數據保證同一個關卡中不存在兩只坐標完全相同的小豬。

如果m=0，表示Kiana輸入了一個沒有任何作用的指令。

如果m=1，則這個關卡將會滿足：至多用只小鳥即可消滅所有小豬。

如果m=2,則這個關卡將會滿足：一定存在一種最優解，其中有一只小鳥消滅了至少只小豬。

保證1<=n<=18，0<=m<=2，0<xi,yi<10，輸入中的實數均保留到小數點后兩位。

上文中，符號和分別表示對c向上取整和向下取整

?

輸出格式：

?

對每個關卡依次輸出一行答案。

輸出的每一行包含一個正整數，表示相應的關卡中，消滅所有小豬最少需要的小鳥數量

?

輸入輸出樣例

輸入樣例#1：

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

輸出樣例#1：

1
1

輸入樣例#2：

3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00

輸出樣例#2：

2
2
3

輸入樣例#3：

1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99

輸出樣例#3：

6

說明

【樣例解釋1】

這組數據中一共有兩個關卡。

第一個關卡與【問題描述】中的情形相同，2只小豬分別位于（1.00,3.00)和 (3.00,3.00)，只需發射一只飛行軌跡為y = -x^2 + 4x的小鳥即可消滅它們。

第二個關卡中有5只小豬，但經過觀察我們可以發現它們的坐標都在拋物線 y = -x^2 + 6x上，故Kiana只需要發射一只小鳥即可消滅所有小豬。

【數據范圍】

?

題解：

1.兩兩枚舉，建立所有方案，然后找出可以打掉的豬。

2.然后狀壓dp F[i|way[j]]=min(F[i|way[j]],F[i]+1).

然后是細節：

dp里面不要調用min函數,會被卡.

?

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define add(S,i) (S|=(1<<(i-1)))
using namespace std;
const double EPS=1e-8;
const int N=20;
int n,m;double x[N],y[N];
double jsa(int i,int j){return (x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
}
double jsb(int i,int j){return (x[i]*x[i]*y[j]-x[j]*x[j]*y[i])/(x[i]*x[j]*(x[i]-x[j]));
}
bool pd(double x,double y){return x>y?(x-y<=EPS):(y-x<=EPS);
}
int w[N*N],num=0;bool vis[N];int F[1<<N],mt;
void DP()
{memset(F,127/3,sizeof(F));F[0]=0;for(int i=0;i<mt;i++){for(int j=1;j<=num;j++){if(F[i]+1<F[i|w[j]])F[i|w[j]]=F[i]+1;}}printf("%d\n",F[mt]);
}
void work()
{double aa,bb;scanf("%d%d",&n,&m);mt=(1<<n)-1;for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){if(x[i]==x[j])continue;aa=jsa(i,j);bb=jsb(i,j);if(aa>=0)continue;vis[i]=vis[j]=true;add(w[++num],i);add(w[num],j);for(int k=1;k<=n;k++){if(pd(y[k],aa*x[k]*x[k]+bb*x[k]))vis[k]=true,add(w[num],k);}}}for(int i=1;i<=n;i++)if(!vis[i])add(w[++num],i);DP();
}
void Clear()
{memset(vis,0,sizeof(vis));memset(w,0,sizeof(w));num=0;
}
int main()
{int T;scanf("%d",&T);while(T--){work();Clear();}
}

?