首页 > 代码库 > UVA 11853 [dfs乱搞]
UVA 11853 [dfs乱搞]
/* 大连热身E题 不要低头,不要放弃,不要气馁,不要慌张 题意: 在1000×1000的格子内有很多个炮弹中心,半径给定。 为某人能否从西部边界出发,从东部边界走出。 不能输出不能,能的话输出最北边的入口和出口的坐标。 思路: dfs乱搞题。把炮弹辐射范围连在一起的炮弹看作一个整体,记录下它围起来的边界区域。 然后找到最北边的输出。 */ #include<bits/stdc++.h> using namespace std; double x[1005],y[1005],r[1005]; int n; bool vis[1005]; double mmax=-20000000,mmin1=20000000,mmin2=20000000; void dfs(int pos){ mmax=max(mmax,y[pos]+r[pos]); if(x[pos]<=r[pos]){ mmin1=min(mmin1,y[pos]-sqrt(r[pos]*r[pos]-x[pos]*x[pos])); } if(1000-x[pos]<=r[pos]){ mmin2=min(mmin2,y[pos]-sqrt(r[pos]*r[pos]-(1000-x[pos])*(1000-x[pos]))); } if(y[pos]<=r[pos])mmin1=mmin2=-1000; vis[pos]=1; for(int i=0;i<n;i++){ if(!vis[i]){ if((x[pos]-x[i])*(x[pos]-x[i])+(y[pos]-y[i])*(y[pos]-y[i])<=(r[i]+r[pos])*(r[i]+r[pos])){ dfs(i); } } } } int main() { while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++)scanf("%lf%lf%lf",x+i,y+i,r+i); memset(vis,0,sizeof(vis)); double ans1=1000,ans2=1000; for(int i=0;i<n;i++){ mmax=-20000000; mmin1=20000000; mmin2=20000000; if(!vis[i])dfs(i); if(mmax>=1000){ ans1=min(ans1,mmin1); ans2=min(ans2,mmin2); } } if(ans1<=0||ans2<=0)puts("IMPOSSIBLE"); else printf("0.00 %.2lf 1000.00 %.2lf\n",ans1,ans2); } }
UVA 11853 [dfs乱搞]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。