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沒用

然后這題數據那么小，顯然狀壓

狀壓無非就是處理打掉和沒打掉

那么我們可以預處理每兩個小鳥的軌跡，ab可以數學推導出來，然后計算這個軌跡經過了哪一些點，計算出來之后把經過點的狀態壓出來，我認為有必要貼出來2的冪次方

2^1=2
2^2=4
2^3=8
2^4=16
2^5=32
2^6=64
2^7=128
2^8=256
2^9=512
2^10=1024
2^11=2048
2^12=4096
2^13=8192
2^14=16384
2^15=32768
2^16=65536
2^17=131072
2^18=262144
2^19=524288
2^20=1048576
2^21=2097152
2^22=4194304
2^23=8388608
2^24=16777216
2^25=33554432
2^26=67108864
2^27=134217728
2^28=268435456
2^29=536870912
2^30=1073741824
2^31=2147483648
2^32=4294967296

然后就暴力枚舉全集就完了

重點！！！精度問題，注意在比較相等的時候精度一定要開的足夠小！！！！我就是這么被卡了！！！！請開1e-6

同時還有一個問題，如果有些點只能原點到那里沒有其他任何點經過（就是這個點與其他點組合成的二次函數系數一定是正數），最后直接一個個單獨處理就行了，非常簡單

記住特判n=1

代碼：

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 double x[20],y[20],a,b; 6 int now,s[262150]; 7 double abs(double x){ 8 if(x<0)return -x; 9 return x; 10 } 11 int main() { 12 int T; 13 cin>>T; 14 while(T--) { 15 memset(s,0x3f3f3f3f,sizeof(s)); 16 int n,m; 17 cin>>n>>m; 18 int tot=(1<<n)-1; 19 for(int i=1; i<=n; i++) { 20 cin>>x[i]>>y[i]; 21 } 22 if(n==1){ 23 cout<<1<<endl; 24 continue; 25 } 26 s[0]=0; 27 for(int i=1; i<n; i++) { 28 for(int j=i+1; j<=n; j++) {//進行兩兩枚舉 29 if(x[i]==x[j])continue; 30 now=0; 31 b=(y[j]*x[i]*x[i]-x[j]*x[j]*y[i])*1.0/(x[i]*x[i]*x[j]-x[i]*x[j]*x[j]); 32 a=(y[i]-b*x[i])*1.0/(x[i]*x[i]*1.0); 33 if(a>=0.0)continue; 34 for(int k=1; k<=n; k++) { 35 if(abs((a*x[k]*x[k]+b*x[k])*1.0-y[k]*1.0)<=0.000001) { 36 now+=1<<(k-1); 37 } 38 } 39 for(int k=0; k<=tot; k++) { 40 s[k|now]=min(s[k|now],s[k]+1); 41 } 42 } 43 } 44 for(int i=1;i<=n;i++){ 45 int now=1<<(i-1); 46 for(int j=0;j<=tot;j++){ 47 s[j|now]=min(s[j|now],s[j]+1); 48 } 49 } 50 cout<<s[tot]<<endl; 51 } 52 }

?

轉載于:https://www.cnblogs.com/saionjisekai/p/9535800.html

總結

以上是生活随笔為你收集整理的NOIP2016 D2T3 愤怒的小鸟的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。