性感代码在线求调
查看原帖
性感代码在线求调
916086
yaoshuen楼主2025/1/22 09:28

样例没过但找不到问题

#include <bits/stdc++.h>
using namespace std;
const int N=20;
const double eps=1e-6;
int T;
int n,m,t;
double _a,_b;
double x,y;
struct node{
	double x;
	double y;
};
node a[N];
vector<int>g;
int f[1<<N];
void init(){
	g.clear();
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			if(fabs(a[i].x-a[j].x)<eps) continue;
			_a=a[i].y*a[j].x-a[j].y*a[i].x;
			_a=_a/(a[i].x*a[i].x*a[j].x-a[j].x*a[j].x*a[i].x);
			if(_a>eps) continue;
			_b=a[i].y-_a*a[i].x*a[i].x;
			_b=_b/a[i].x;
			t=0;
			for(int k=1;k<=n;k++){
				if(fabs(a[k].x*a[k].x*_a+a[k].x*_b-a[k].y)<eps){
					t=t|(1<<(k-1));
				}
			}
			g.push_back(t);
		}
	}
}
void solve(int _n){
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<_n;j++){
			f[i|g[j]]=min(f[i|g[j]],f[i]+1);
		}
	}
	printf("%d\n",f[(1<<n)-1]);
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%lf%lf",&x,&y);
			a[i]=node{x,y};
		}
		init();
		solve((int)g.size());
	}
	return 0;
}
2025/1/22 09:28
加载中...