求助,悬两关
查看原帖
求助,悬两关
1073741
UKE_bound楼主2024/8/8 13:25
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const double eps=1e-9;
int m,n,k;
struct vep{
	int x,y;
};
struct bom{
	int x,y;
	int h=0;
	int wc[maxn];
};
vep v[maxn];
bom bo[maxn];
bool check(int a,int c){
	bom t1=bo[a];
	vep t2=v[c];
	int x1=t1.x,y1=t1.y;
	int x2=t2.x,y2=t2.y;
	return (k-hypot(x2-x1,y2-y1))>eps;
}
bool b[maxn];
int ans=0x3fffffff;
void dfs(int d,int a){
	if(a==m){
		ans=min(ans,d);
		return;
	}else if(d==n){
		return;
	}
	for(int i=1;i<=m;i++){
		if(b[i])continue;
		int *r=bo[i].wc;
		int j=find(r,r+bo[i].h,a+1)-r;
		if(j==bo[i].h){
			continue;
		}else{
			b[i]=1;
			d++;
			int t=a;
			for(int k=j;k<min(j+300,bo[i].h);k++){
				if(k==j){
					a++;
					if(a==m){
						dfs(d,a);
					}
					continue;
				}
				if(r[k]!=r[k-1]+1){
					dfs(d,a);
				}
				a++;
				if(a==m){
					dfs(d,a);
				}
			}
			a=t;
			d--;
			b[i]=0;
		}
	}
}
int main(){
	cin>>m>>n>>k;
	for(int i=1;i<=m;i++){
		cin>>v[i].x>>v[i].y;
	}
	for(int i=1;i<=n;i++){
		cin>>bo[i].x>>bo[i].y;
		for(int j=1;j<=m;j++){
			if(check(i,j)){
				bo[i].wc[bo[i].h++]=j;
			}
		}
	}
	dfs(0,0);
	cout<<ans;
	return 0; 
}

码了两个小时,调了半个小时后,喜提TLE

2024/8/8 13:25
加载中...