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
     
       2 #include
      
        3 #include
       
         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<
        
         >x[i]>>y[i];21         }22         if(n==1){23             cout<<1<
         
          =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<
          
           <