问题源自P2831 [NOIP2016 提高组] 愤怒的小鸟。此题中,我的代码使用了 fabs,但是发现 fabs(a-b)!=fabs(b-a),以至于我只能手写 abs。具体如下。
#include <bits/stdc++.h>
using namespace std;
namespace math{
double ffabs(double x){
return (x<0?-x:x);
}
}
using namespace math;
const int N=20;
const double eps=1e-8;
int T;
int n,m;
double x[N],y[N];
int line[N][N],f[1<<N];
void solve(double &x,double &y,double a,double b,double c,double d,double e,double f){
x=(c*e-b*f)/(a*e-b*d);
y=(c*d-a*f)/(b*d-a*e);
return;
}
int main(){
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
memset(line,0,sizeof(line));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ffabs(x[i]-x[j])<eps) continue; //不存在竖的二次函数
double a,b;
solve(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);
if(a>-eps) continue;
for(int k=1;k<=n;k++){
cout<<fabs(double(a*x[k]*x[k]+b*x[k]-y[k]))<<":"<<fabs(double(y[k]-a*x[k]*x[k]+b*x[k]))<<endl;
if(ffabs(a*x[k]*x[k]+b*x[k]-y[k])<eps){
line[i][j]|=(1<<(k-1));
}
}
}
}
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=0;i<(1<<n);i++){ //只能递推吧
for(int j=1;j<=n;j++){
f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+1);
if(!((i>>(j-1))&1)){ //没有
for(int k=1;k<=n;k++){
f[i|line[j][k]]=min(f[i|line[j][k]],f[i]+1); //不管有没有打过,一起穿了
}
}
}
}
cout<<f[(1<<n)-1]<<endl;
}
return 0;
}
测试代码在33行。输入题目中的样例2,出来的数基本都不一样。求为什么(QAQ)。