我的代码:
#include<bits/stdc++.h>
#define db double
using namespace std;
const db eps=1e-6;
db x[20],y[20];
int f[530000],line[20][20];
struct node{
db x,y;
};
inline int read()
{
int x=0;
bool w=0;
char c=getchar();
while(!isdigit(c))
w|=c=='-',c=getchar();
while(isdigit(c))
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
inline node fun(db x1,db y1,db x2,db y2)
{
db a=(x2*y1-x1*y2)/(x1*x1*x2-x2*x2*x1);
db b=(y1-a*x1*x1)/x1;
return (node){a,b};
}
inline bool check(int k,db a,db b)
{
db xx=x[k],yy=y[k];
return fabs((double)(xx*xx*a+xx*b-yy))<eps;
}
int main()
{
ios::sync_with_stdio(false);
int T=read();
while(T--)
{
memset(line,0,sizeof(line));
memset(f,127,sizeof(f));
int n=read(),m=read();
for(register int i=1;i<=n;++i)
cin>>x[i]>>y[i];
for(register int i=1;i<n;++i)
for(register int j=i+1;j<=n;++j)
{
if(fabs(x[i]-x[j])<=eps) continue;
node t=fun(x[i],y[i],x[j],y[j]);
db a=t.x,b=t.y;
if(a>-eps) continue;
for(register int k=1;k<=n;++k)
if(check(k,a,b)) line[i][j]|=(1<<(k-1));
}
f[0]=0;
for(register int i=0;i<(1<<n)-1;++i)
{
register int j=0;
for(register int l=1;l<=n;++l)
if((i&(1<<(l-1)))==0)
{
j=l;
break;
}
f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+1);
for(register int k=j+1;k<=n;++k)
{
if((i&(1<<(k-1)))!=0) continue;
f[i|line[j][k]]=min(f[i|line[j][k]],f[i]+1);
}
}
printf("%d\n",f[(1<<n)-1]);
}
return 0;
}
第一个样例输入:
10
1 0
0.79 1.72
1 0
4.38 5.62
2 0
2.27 0.62
6.40 7.87
1 0
9.86 4.10
1 0
2.28 6.10
2 0
1.16 6.35
1.63 4.85
2 0
0.45 4.73
3.96 1.91
2 0
4.74 0.82
5.16 9.11
1 0
5.44 8.56
2 0
1.85 3.63
2.94 8.89
我的输出:
1
1
2
1
1
1
1
2
1
2
样例输出
1
1
2
1
1
1
1
2
1
2
我给的评测结果用了freopen,所以可以保证没有任何问题,没有自己手滑啥的
我可能是眼睛不好吧,请问这个测试点输出和我的有什么区别吗?
我的结果是全WA欸(