超级晕晕晕
查看原帖
超级晕晕晕
199459
Masna_Kimoyo楼主2021/10/2 20:59

我的代码:

#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欸(

2021/10/2 20:59
加载中...