- 浏览: 199383 次
- 性别:
- 来自: 广州
文章分类
最新评论
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何时变得如此垃圾的...
sophisticated methods for emergent information processing in decentralized spatially extended systems. The mechanisms underlying the resulting emergent computation are explicated by a technique for ...
pdf 英文版。2009 jolt award
Emergent Abilities of Large Language Models.pdf
Emergent Mercenary是一种具有战略意义的3D FPS,并且是新兴游戏中的精粹。 仅通过将具有特定AI的角色放置到游戏中并看到他们互动,就可以轻松设置场景(例如,追捕犯罪分子)。
emergent_abilities_of_large_la.pdf
文献Emergent simplicity in microbial community assembly中使用的模型原始代码
Cooperation Oriented Computing: A Computing Model Based on Emergent Dynamics of Group Cooperation
Emergent.Design - The Evolutionary Nature of Professional Software Development-Mar.2008-Addison Wesley.chm
The future of the World Wide Web depended on its ability to understand and automatically process content to enable computers and people to work in cooperation. New advanced techniques and intelligent ...
附件为链接文件 Gamebryo.3.0 LightSpeed 详情请自行搜索,该资源 来源于互联网。 安装后目录,大小为10G左右 ├─Build │ ├─CoreRuntime │ │ └─Win32 │ │ ├─VC80 │ │ │ └─Property Sheets ...
新兴技术 了解2021年的最佳技能需求 技术能力 : 内容 : 人工智能 区块链 云计算 网络安全 数据科学 新兴技术介绍 混合云 物联网(IoT) 大型机 开源技术 编程和编码 入门 - - 网页: ...学习技巧
简单句法习得计算模型的影响因素分析,余昊,王小捷,本文旨在研究儿童语言习得计算模型的外部语言输入和内部参数对系统学习、理解、产生简单句法的影响。以一个模拟儿童语言一词阶段
三种挺水植物抗性生理生态特性研究,孙瑞莲,刘健,利用小型模拟人工湿地生态系统,研究宽叶香蒲、茭白及黄花鸢尾对含 COD/N/P污水的净化能力及其抗性生理生态特征。研究结果表明:(1
emergent_comm_rl 此仓库将包含在“具有符号和像素输入的参照游戏的语言交流的出现”中使用的强化学习模型。 该文件可以在找到。 我们是否可以通过具有信息不对称特征的合作任务,促使强化学习者学习组成语言? 环境...
斯科特·斯奈德紧急代码挑战
An Emergent Wall Following Behaviour to Escape Local Minima for Swarms of Agents 多智能体,沿墙走,突显行为,局部极小点,人工势场法,APF,wall following behavior,local minimum
The school sociologist: A need and an emergent profession. Washington, D.C.: University Press of America, 261 pp., [dollar]12.95 (paper) Book Reviews 5 3 3 In Chapter Seven, Day, McCollum, ...