- 浏览: 204185 次
- 性别:
- 来自: 广州
文章分类
最新评论
Emergent escape
Time Limit : 3000/1000ms (Java/Other)
Memory Limit : 65535/32768K (Java/Other)
Problem Description
In the year 23XX, spaceship is very popular used in transmission of the universe. People live not only on the earth, but also on many other planets. I am an astronaut, professionally speaking, a captain. I have my own spaceship, which names “ZEPHYR”. My job is that exploring the galaxy, detecting the mines and gas, collecting the swatch and bringing them to the earth.
I love my job. It is so excited that traveling through the stars. I’m always accidentally meeting many graceful things I
have never seen before, but sometimes it is not so good when bad lucks fall off.
One day, when I am driving my spaceship, dangers happened. I find that I have gone a wrong way, there are lots of aerolites in my frontage, and they are gonna to strike my spaceship within a few seconds. I try to control the ship to avoid hitting, but there are really too much aerolites. Finally, my spaceship is badly damaged. Oh, my “ZEPHYR”!
But there is no time to be sad. I hear the warning of the computer: “Emergency! The spaceship is going to explode!” I have to escape immediately! There is a life-ship in a corner of the spaceship. Now I am in the controlling room, another side of the spaceship. Do I have chance to get away?
Seeing from frontward to backward, “ZEPHYR” is shaped as a circle, we defined the coordinates of the center of the circle is (0,0), the radius is R, and the angle of the East is 0°, the angle of the North is 90°. My computer has detected out there are N aerolites stroke my spaceship. Each aerolite is also shaped as a circle, with location coordinates (xi,yi), and radius ri. If it hits my spaceship, it leaves a hole as its shape, so I cannot get through it. The controlling room and the life-ship are all on the circumference (Compared with the huge spaceship, you could assume both of them as a point), with their angles d1 and d2, anti-clockwise from East. Tell me whether I can get to the life-ship. I can go to everywhere in my spaceship, except the hole hit by the aerolites (Even the edge of the hole).
Input
The first line of input there is one integer T (T<=100), giving the number of test cases in the input. Each test case starts with a line containing three real number R, d1, d2 (0<R<=10000, 0<=d1,d2<360, d1≠d2) , representing the radius of the spaceship, and the degree of the two place on the circumference. Next line is a positive integer N (0<N<=1000), the number of the aerolites. Then N lines each line comes with a coordinate (xi,yi), and radius ri, all of them are real number, (-10000<=xi,yi<=10000, 0<ri<=10000). There is a blank line between each test case.
Note that some aerolites may not strike on the spaceship, and some aerolites may directly strike on the controlling room or life-ship, even the edge of the aerolites (How poor! Then you die hard!).
Output
For each test case, output a string:
“Escape!”, if you could reach the life-ship.
“Die hard!”, if you fail to reach the life-ship, or the controlling room or life-ship is directly struck by some aerolites.
Sample Input
2
10 240 45
4
0 0 7
-7 7 4
15 5 3
6 -5 2
1 0 1
1
0 0 10000
Sample Output
Escape!
Die hard!
题目大意:有一部飞船,遇到好多陨石,那些陨石将会砸烂那部飞船,那些陨石是阻碍你的东西。遇到这种情况,我要从驾驶舱到安全舱,问能否去到?
//Emergent escape //几何+并查集(想到用并查集,这题就变得简单!!!) #include <iostream> #include <stdio.h> #include <cmath> using namespace std; const double PI = 3.14159265358979; const double eps = 1e-8; struct point { double x,y,r; bool fa,ok; }a[1010]; point p1,p2; //p1、p2是那出逃的两个点 int father[1010]; double r; double dist_1point(point a1) //点到原点距离 { return sqrt(a1.x*a1.x+a1.y*a1.y); } double dist_2point(point a1,point a2) //两点之间距离 { return sqrt((a1.x-a2.x)*(a1.x-a2.x)+(a1.y-a2.y)*(a1.y-a2.y)); } double dist_2point(double x1,double y1,double x2,double y2) //两点之间距离 { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } ///并查集三部曲 1.make 2.find 3.Union void make(int n) //初始化老豆 { for(int i=0;i<n;i++) { father[i]=i; } } /*int find(int x) //找老豆1(容易写、容易记) { if(x!=father[x]) { father[x]=find(father[x]); } return father[x]; }*/ int find(int x) //找老豆2(速度快、防止递归太深) { int rr=x; while(father[rr]!=rr) { rr=father[rr]; } int j,i=x; while(i!=rr) { j=father[i]; father[i]=rr; i=j; } return rr; } void Union(int x,int y) //合并 { father[y]=x; } bool line_3point(point a1,point a2,point a3) //求点在直线的左边还是右边。(叉乘) { double P,Q,M; P=(a2.x - a1.x) * (a3.y - a1.y); Q=(a3.x - a1.x) * (a2.y - a1.y); M=P-Q; if(M>0) return false; //正数 说明在向量的右边,是顺时针旋转的。 if(M<0) return true; //负数 说明在向量的左边,是逆时针旋转的。 if(M==0) return true; //零 说明线段的直线上,则点(x3,y3)是共线。 return false; } int main() { int t,i,j,n,fa,fb; double d1,d2,x1,y1,x2,y2; double len1,len2; bool flag; scanf("%d",&t); while(t--) { flag=false; scanf("%lf%lf%lf",&r,&d1,&d2); if(d1>d2) swap(d1,d2); //d1<d2,方便计算 ///求那两个点的坐标(用三角函数求坐标会有些小误差) x1=r*cos(d1*PI/180.0); y1=r*sin(d1*PI/180.0); x2=r*cos(d2*PI/180.0); y2=r*sin(d2*PI/180.0); p1.x=x1; p1.y=y1; p2.x=x2; p2.y=y2; ///求完p1(x1,y1)、p2(x2,y2) scanf("%d",&n); make(n); //初始化 for(i=0;i<n;i++) { scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r); if(flag) continue; //判断是否已经碰撞了 len1=dist_2point(a[i],p1); len2=dist_2point(a[i],p2); if(len1-eps<=a[i].r) //注意!计算误差! flag=true; if(len2-eps<=a[i].r) //注意!计算误差! flag=true; if(dist_1point(a[i])>a[i].r+r) //若相离 { a[i].ok=false; a[i].fa=false; } else a[i].ok=true; if(a[i].ok) //若不相离 { if(dist_1point(a[i])<r-a[i].r) //若内含 a[i].fa=false; else a[i].fa=true; //相交则老豆标记true } } if(flag) //已经碰撞的直接输出 { printf("Die hard!\n"); continue; } for(i=0;i<n;i++) { if(a[i].ok==false) continue; for(j=i+1;j<n;j++) { if(a[j].ok==false) continue; if(dist_2point(a[i],a[j])-eps<=a[i].r+a[j].r) { if(a[i].fa && a[j].fa) { double x0,y0,x1,y1,x2,y2,l,k1,k2,R2,AE,EF,dd1,dd2; point a1,a2,a3; a1=a[i]; a2=a[j]; a3.x=a3.y=0; ///改变坐标求交点(计算更方便) a1.x-=a2.x; a1.y-=a2.y; a3.x-=a2.x; a3.y-=a2.y; a2.x-=a2.x; a2.y-=a2.y; //求交点(x1,y1)、(x2,y2) if(a1.x==0) { y1=y2=(a2.r*a2.r-a1.r*a1.r+a1.y*a1.y)/(2*a1.y); x1=sqrt(a2.r*a2.r-y1*y1); x2=-x1; } else if(a1.y==0) { x1=x2=(a2.r*a2.r-a1.r*a1.r+a1.x*a1.x)/(2*a1.x); y1=sqrt(a2.r*a2.r-x1*x1); y2=-y1; } else { k1=a1.y/a1.x; k2=-1/k1; l=sqrt(a1.x*a1.x+a1.y*a1.y); AE=(a2.r*a2.r-a1.r*a1.r+l*l)/(2*l); x0=a1.x*AE/l; y0=k1*x0; R2=fabs(a2.r*a2.r-x0*x0-y0*y0); EF=sqrt(R2/(1+k2*k2)); x1=x0-EF; y1=y0+k2*(x1-x0); x2=x0+EF; y2=y0+k2*(x2-x0); } dd1=dist_2point(x1,y1,a3.x,a3.y); dd2=dist_2point(x2,y2,a3.x,a3.y); if(dd1>r && dd2>r) //如果两个交点都在大圆外面,则不合并 continue; } //若两个交点都在园内 fa=find(i); //找老豆 fb=find(j); //找老豆 if(fa!=fb) //若老豆不相同,合并! { father[fa]=fb; //随便合并都行,连住就是同一个老豆! } } } } double x0,y0,x1,y1,x2,y2,x3,y3,x4,y4; double l,k1,k2,R2,AE,EF,sita1,sita2; for(i=0;i<n;i++) { if(flag) break; //求出了直接break退出 if(a[i].fa==true) { for(j=i+1;j<n;j++) { if(a[j].fa==true) { fa=find(i); fb=find(j); if(fa==fb) { bool xx=line_3point(p1,p2,a[i]); bool yy=line_3point(p1,p2,a[j]); if((xx==true && yy==true) || (xx==false && yy==false)) { //若两个圆心都在白色两点的连线的同一边,则肯定可以通过 continue; } ///可以当做圆与以原地为圆心的圆的交点的模板!!! ///求圆与大圆的一个交点(x1,y1)或(x2,y2) if(a[i].x==0) { y1=y2=(r*r-a[i].r*a[i].r+a[i].y*a[i].y)/(2*a[i].y); x1=sqrt(r*r-y1*y1); x2=-x1; } else if(a[i].y==0) { x1=x2=(r*r-a[i].r*a[i].r+a[i].x*a[i].x)/(2*a[i].x); y1=sqrt(r*r-x1*x1); y2=-y1; } else { k1=a[i].y/a[i].x; k2=-1/k1; l=sqrt(a[i].x*a[i].x+a[i].y*a[i].y); AE=(r*r-a[i].r*a[i].r+l*l)/(2*l); x0=a[i].x*AE/l; y0=k1*x0; R2=fabs(r*r-x0*x0-y0*y0); EF=sqrt(R2/(1+k2*k2)); x1=x0-EF; y1=y0+k2*(x1-x0); //x2=x0+EF; //y2=y0+k2*(x2-x0); } sita1=atan2(y1,x1)*180/PI; //用atan2求出的数是弧度,要化为角度 if(sita1<0) sita1+=360; //若小于0,加上360变正 ///并求出交点在圆的哪个角度 ///求另外一个圆与大圆的交点(x3,y3)、(x4,y4) if(a[j].x==0) { y3=y4=(r*r-a[j].r*a[j].r+a[j].y*a[j].y)/(2*a[j].y); x3=sqrt(r*r-y3*y3); x4=-x3; } else if(a[j].y==0) { x3=x4=(r*r-a[j].r*a[j].r+a[j].x*a[j].x)/(2*a[j].x); y3=sqrt(r*r-x3*x3); y4=-y3; } else { k1=a[j].y/a[j].x; k2=-1/k1; l=sqrt(a[j].x*a[j].x+a[j].y*a[j].y); AE=(r*r-a[j].r*a[j].r+l*l)/(2*l); x0=a[j].x*AE/l; y0=k1*x0; R2=fabs(r*r-x0*x0-y0*y0); EF=sqrt(R2/(1+k2*k2)); x3=x0-EF; y3=y0+k2*(x3-x0); //x4=x0+EF; //y4=y0+k2*(x4-x0); } sita2=atan2(y3,x3)*180/PI; if(sita2<0) sita2+=360; ///求交点完毕、并求出交点在圆上的角度 if(sita1>sita2) swap(sita1,sita2); ///注意!!!之前在这里犯了严重错误,漏了一种情况未考虑到! if((sita1>d1 && sita1<d2 && sita2>d2 && sita2<d1+360) || (sita1>d2-360 && sita1<d1 && sita2>d1 && sita2<d2)) { flag=true; break; } } } } } } if(flag==true) printf("Die hard!\n"); else printf("Escape!\n"); } return 0; }
相关推荐
Emergent Design The Evolutionary Nature of Professional Software Development 原版书籍 中文名字:浮现式设计:专业软件开发的演进本质 csdn上怎么来了些混蛋,一本电子书还要很多积分,csdn何时变得如此垃圾的...
pdf 英文版。2009 jolt award
《 Emergent Mercenary - 开源游戏的创新与技术解析》 在当今的数字娱乐领域,开源软件已经成为一种不可忽视的力量,特别是在游戏开发中。"Emergent Mercenary"就是这样一款以战略性和3D第一人称射击(FPS)玩法相...
### 演化中的涌现计算 #### 摘要与背景 本文《演化中的涌现计算》探讨了简单进化过程如何在分散的、空间扩展的系统中发现复杂的涌现信息处理方法。这种类型的计算不仅对理解自然信息处理至关重要,还为新型并行...
Emergent.Design - The Evolutionary Nature of Professional Software Development-Mar.2008-Addison Wesley.chm
### 知识点一:语义网(Semantic Web) #### 定义与概念 - **语义网**:是万维网的一种理想形式,旨在使网络数据具备机器可理解的意义,从而实现自动化处理和智能应用。它通过为网页中的数据添加元数据(描述数据的...
"mcrm-master.zip"是一个压缩包文件,其中包含了《Emergent simplicity in microbial community assembly》这篇文献中所使用的原始代码。这篇研究论文探讨了微生物群落构建过程中的涌现简单性,即在看似复杂的生态...
《大规模语言模型的涌现能力》 这篇论文发表在2022年8月的《机器学习研究交易》上,主要探讨了大型语言模型的一个不可预测现象——“涌现能力”。作者们来自谷歌、斯坦福大学、北卡罗来纳大学教堂山分校和DeepMind...
《大规模语言模型的涌现能力》 这篇论文发表在2022年8月的《机器学习研究交易》中,探讨了大型语言模型的涌现能力。文章由来自谷歌、斯坦福大学、北卡罗来纳大学教堂山分校和DeepMind的研究人员共同撰写。...
新兴技术 了解2021年的最佳技能需求 技术能力 : 内容 : 人工智能 区块链 云计算 网络安全 数据科学 新兴技术介绍 混合云 物联网(IoT) 大型机 开源技术 编程和编码 入门 - - 网页: ...学习技巧
本研究聚焦于三种挺水植物——宽叶香蒲、茭白和黄花鸢尾对污水中的化学需氧量(COD)、氮(N)和磷(P)浓度变化的生态生理特性研究。研究采用了人工模拟湿地生态系统的微缩模型,通过对比有植物和无植物的微缩湿地模型,...
Scaling, Emergence, and ...Scaling,Emergence 和 Reasoning 是大型语言模型中的三个重要概念,它们紧密相连, Scaling 带来了 Emergent Abilities,而 Emergent Abilities 又使得语言模型具备了 Reasoning 的能力。
emergent_comm_rl 此仓库将包含在“具有符号和像素输入的参照游戏的语言交流的出现”中使用的强化学习模型。 该文件可以在找到。 我们是否可以通过具有信息不对称特征的合作任务,促使强化学习者学习组成语言? 环境...
在"emergent-design-master"这个文件夹中,可能包含了实现生命游戏和上述编程实践的源代码和相关资源。通过分析这些代码,可以深入学习如何在实际项目中应用应急设计和相关编程原则。这个练习不仅可以提升编程技能,...
斯科特·斯奈德(Scott Snyder)的“紧急代码挑战”是一个可能的编程或软件开发练习,旨在提升开发者在面对紧急情况时解决问题的能力。这个挑战可能是为了模拟真实世界中的编程危机,例如修复严重错误、优化性能或者...
An Emergent Wall Following Behaviour to Escape Local Minima for Swarms of Agents 多智能体,沿墙走,突显行为,局部极小点,人工势场法,APF,wall following behavior,local minimum