首页 > 代码库 > 【DFS】Paintball(6-22)

【DFS】Paintball(6-22)

2024-11-19 19:50:02   206人阅读

[UVA11853]Paintball

算法入门经典第6章6-22(P175)

题目大意：有一个1000*1000的正方形战场，西南角坐标(0,0)，西北角坐标(0,1000)，有n个敌人，每个敌人处在(xi,yi),攻击范围为ri，要避开他们的攻击范围，求从最左边出发的最北边出发点及右边的最北边到达点。

试题分析：我们先判断是否能有方案，如何判断？将相交圆的圆心相连，看从交上边界的圆出发是否能到达与下边界相交的圆。然后再这个过程中如果看到与左/右边界相交的圆那么更新答案就好了。

#include<iostream>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#include<stack>#include<algorithm>using namespace std;inline int read(){	int x=0,f=1;char c=getchar();	for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;	for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;	return x*f;}const int MAXN=2001;const int INF=999999;int N,M;vector<int> vec[MAXN];struct data{	double x,y,r;}cir[MAXN];bool vis[MAXN];double ansl,ansr;bool flag=false;double dis(int a,int b){	double x=cir[a].x-cir[b].x;	double y=cir[a].y-cir[b].y;	return sqrt(x*x+y*y);}bool DFS(int x){	if(vis[x]||flag) return false;	vis[x]=true;	if(cir[x].x-cir[x].r<=0){		flag=true;		return true;	}	if (cir[x].y<=cir[x].r) ansl=min(ansl,cir[x].x-sqrt(cir[x].r*cir[x].r-cir[x].y*cir[x].y));      if (cir[x].y+cir[x].r>=1000) {    	double k=1000-cir[x].y;		ansr=min(ansr,cir[x].x-sqrt(cir[x].r*cir[x].r-k*k));	}	for(int i=0;i<vec[x].size();i++) DFS(vec[x][i]);	return false;}int main(){	while(scanf("%d",&N)!=EOF){		for(int i=1;i<=N;i++) vec[i].clear();		ansl=ansr=1000.0; flag=false;		for(int i=1;i<=N;i++){			scanf("%lf",&cir[i].y);			scanf("%lf",&cir[i].x);			scanf("%lf",&cir[i].r);		}		for(int i=1;i<N;i++){			for(int j=i+1;j<=N;j++){				if(dis(i,j)<=cir[i].r+cir[j].r){					vec[i].push_back(j);					vec[j].push_back(i);				}			}		}		memset(vis,false,sizeof(vis));		for(int i=1;i<=N;i++)			if(cir[i].r+cir[i].x>=1000)				if(DFS(i)) break;		if(flag) printf("IMPOSSIBLE\n");          else printf("%.2f %.2f %.2f %.2f\n",0.0,ansl,1000.0,ansr);	}}

【DFS】Paintball(6-22)


联系
我们