愤怒的小鸟
- n很小考虑用状态压缩，先预处理出每两个坐标得到的抛物线可以打掉那些点（用状压）
- (O(n^22^n))的较为简单
- 考虑一个优化，在没每个状态在转移的时候，用二进制下第一位为0（因为这个猪一定需要被打掉不管先后）（其实先做第二位为0，第三维..都一样）
- 这样就可以优化掉一维
- 注意要适当卡精度，用long double，比较的时候，加上一个误差（1e-6~1e-10)
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define U(i,u) for(register int i=head[u];i;i=nxt[i])
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define per(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> PII;
typedef vector<int> VI;
template<class T> inline void read(T &x){
x=0;char c=getchar();int f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;
}
template<class T> inline void cmin(T &x, T y){x=x<y?x:y;}
template<class T> inline void cmax(T &x, T y){x=x>y?x:y;}
const int N=20;
const ld ex=1e-10;
int f[1<<N];
int n,m;
ld x[N],y[N];
int num[N],cnt;
int s[N][N];
void makes(){
// for(int mask=0;mask<(1<<n);mask++){
// f[mask]=20;s[mask]=0;
// cnt=0;bool flag=0;
// rep(i,1,n){
// if(mask&(1<<(i-1))){
// num[++cnt]=i;
// if(cnt==2){
// a=(y[num[1]]*x[num[2]]-y[num[2]]*x[num[1]])/(x[num[1]]*x[num[1]]*x[num[2]]-x[num[2]]*x[num[2]]*x[num[1]]);
// if(a>=0){flag=1;break;}
// b=(y[num[1]]*x[num[2]]*x[num[2]]-y[num[2]]*x[num[1]]*x[num[1]])/(x[num[1]]*x[num[2]]*x[num[2]]-x[num[2]]*x[num[1]]*x[num[1]]);
// }else if(cnt>2){
// ld abs=a*x[num[cnt]]*x[num[cnt]]+b*x[num[cnt]]-y[num[cnt]];
// if(abs<0)abs=-abs;
// if(abs>0.000001){flag=1;break;}
// }
// }
// }
// if(flag)continue;
// s[mask]=1;
// }
rep(i,0,(1<<n)-1)f[i]=20;
f[0]=0;
rep(i,1,n)rep(j,1,n)s[i][j]=0;
rep(i,1,n){
rep(j,i+1,n){
if(x[i]==x[j])continue;
ld a=(y[i]*x[j]-y[j]*x[i])/(x[i]*x[i]*x[j]-x[j]*x[j]*x[i]);
if(a>=0)continue;
ld b=(y[i]*x[j]*x[j]-y[j]*x[i]*x[i])/(x[i]*x[j]*x[j]-x[j]*x[i]*x[i]);
int mask=0;
rep(k,1,n)if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<ex)mask|=(1<<(k-1));
s[i][j]=mask;
}
}
}
int main(){
int T;read(T);
while(T--){
read(n);read(m);rep(i,1,n)scanf("%Lf %Lf",&x[i],&y[i]);
makes();
for(int i=0;i<(1<<n);i++){
rep(j,1,n){
if(!(i&(1<<(j-1)))){
rep(k,j,n){
if(j==k)cmin(f[i|(1<<(j-1))],f[i]+1);
else if(x[j]==x[k]<ex)continue;
else cmin(f[i|s[j][k]],f[i]+1);
}
break;
}
}
}
printf("%d
",f[(1<<n)-1]);
}
return 0;
}
/*
1
3 0
9.00 8.91
3.00 2.99
0.01 0.01
ans=2
2
2 0
1.00 3.00
3.00 3.00
5 0
0.01 0.19
0.02 0.38
0.03 0.57
0.04 0.76
0.05 0.95
ans=1 5
*/