1071: 圣斗士黃金十二宮（七）銀河星爆

Time Limit:?500 MS??Memory Limit:?64 MB
Submit:?193??Solved:?10
[Submit][Status][Web Board]

Description

　　撒加回答了星矢的第一個問題，但是當星矢要問第二個問題時，撒加的頭發全變白了。白撒加的實力是無人能及的，星矢被廢去了五感。這時幫沙加統計完單詞的一輝也趕到了，想打贏白撒加是不可能的，一輝的目標就是爭取時間讓星矢拿到銅盾。為了盡快打倒被稱為不死鳥的一輝，撒加也使出生平絕技---即使是星星被擊中也要粉碎的銀河星爆。
從撒加放出銀河星爆到銀河星爆接近一輝需要一段時間，在這段時間里一輝可以朝任何方向移動k單位的距離來躲開銀河星爆。銀河星爆的橫截面為一個圓形，顯然一輝在與橫截面平行的平面上移動可以以最大的概率躲過。在該平面上建立直角坐標系橫軸為x縱軸為y，銀河星爆的橫截面圓心坐標為(x1, y1)，半徑為R1。
把一輝也當成一個圓，他在坐標系上朝任意方向移動的最大距離為k，考慮到地形因素和一輝個人能力，一輝所能移動到的點(x , y)需滿足0 <= x <= 1000 , 0 <= y <= 1000。如果兩個圓不相交則說明一輝躲過了銀河星爆（注意兩圓外切也說明一輝躲過了）。
現在請您預測一輝能否有可能躲過撒加的銀河星爆。

Input

　　第一行為三個整數x₁, y₁, R₁，代表銀河星爆的圓心坐標和半徑，其中0<= x₁, y₁?<= 1000, 0 < R₁?<= 300。
第二行為三個整數x₂, y₂, R₂，代表一輝的圓心坐標和半徑，其中0 <= x₂, y₂?<= 1000, 0 < R₂?<= 30。
第三行為一個正整數k <= 2000 表示一輝可以移動的最長距離。

Output

　　如果一輝可以躲過銀河星爆則輸出"Yes"，否則輸出"No"（不包含引號）。

Sample Input

900 900 250
950 950 30
316

Sample Output

Yes

HINT

Source

廈門大學第五屆程序設計競賽 第二次網絡預賽 @ kantianfadai

[Submit][Status][Web Board]

?

題目鏈接：

　　http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1071

題目大意：

　　一個炸彈，坐標（X1,Y1），爆炸半徑R1，一個人，坐標（X2，Y2），視為球體半徑R2，人最多移動距離為K，問能否躲過炸彈且圓心不超出邊界。（外切或相離）

題目思路：

　　【計算幾何】

　　首先將人的體積半徑算在爆炸范圍內，即R1=R1+R2。人的運動范圍也為一個圓R2=K。這樣確定了兩個圓。

　　分情況考慮，在不超界的情況下，如果相離或相切（圓心距離>=半徑和）則可行。

　　如果相交，則優先考慮按圓心連線的方向逃離是否可行，是否超界。

　　若超界則求圓的交點，若交點有一個在邊界內則可行。

　　內含不可行。

?

1 /**************************************************** 2 3 Author : Coolxxx 4 Copyright 2017 by Coolxxx. All rights reserved. 5 BLOG : http://blog.csdn.net/u010568270 6 7 ****************************************************/ 8 #include<bits/stdc++.h> 9 #pragma comment(linker,"/STACK:1024000000,1024000000") 10 #define abs(a) ((a)>0?(a):(-(a))) 11 #define lowbit(a) (a&(-a)) 12 #define sqr(a) ((a)*(a)) 13 #define mem(a,b) memset(a,b,sizeof(a)) 14 const double EPS=0.00001; 15 const int J=10; 16 const int MOD=100000007; 17 const int MAX=0x7f7f7f7f; 18 const double PI=3.14159265358979323; 19 const int N=124; 20 using namespace std; 21 typedef long long LL; 22 double anss; 23 LL aans; 24 int cas,cass; 25 int n,m,lll,ans; 26 27 struct Point 28 { 29 double x, y; 30 Point(double x = 0, double y = 0) :x(x), y(y) {} 31 }; 32 33 typedef Point Vector; 34 35 Vector operator - (Point A, Point B) 36 { 37 return Vector(A.x - B.x, A.y - B.y); 38 } 39 40 Vector operator + (Vector A, Vector B) 41 { 42 return Vector(A.x + B.x, A.y + B.y); 43 } 44 45 Vector operator * (Vector A, double p) 46 { 47 return Vector(A.x * p, A.y * p); 48 } 49 50 Vector operator / (Vector A, double p) 51 { 52 return Vector(A.x / p, A.y / p); 53 } 54 55 double Dot(Vector A,Vector B) 56 { 57 return A.x * B.x + A.y * B.y; 58 } 59 60 double Length(Vector A) 61 { 62 return sqrt(Dot(A,A)); 63 } 64 65 double Angle(Vector A,Vector B) //求角度 66 { 67 return acos(Dot(A,B) / Length(A) / Length(B)); 68 } 69 70 double angle(Vector v) 71 { 72 return atan2(v.y,v.x); 73 } 74 75 const double eps = 1e-10; 76 int dcmp(double x) 77 { 78 if(fabs(x) < eps) return 0; 79 else 80 return x < 0 ? -1 : 1; 81 } 82 83 bool operator < (const Point& a,const Point& b) 84 { 85 return a.x < b.x || (a.x == b.x && a.y < b.y); 86 } 87 88 bool operator == (const Point& a,const Point &b) 89 { 90 return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; 91 } 92 93 struct Circle 94 { 95 Point c; 96 double r; 97 Circle(Point c, double r) :c(c), r(r) {} 98 Point point(double a) 99 { 100 return Point(c.x + cos(a) * r, c.y + sin(a) * r); 101 } 102 }; 103 104 int getCircleCircleIntersection(Circle C1,Circle C2,vector<Point>& sol) //求圓和圓的交點 105 { 106 double d = Length(C1.c - C2.c); 107 if(dcmp(d) == 0) //首先圓心要重合 108 { 109 if(dcmp(C1.r - C2.r) == 0) return -1; //其次半徑要相同，然后就可以推出兩圓重合 110 return 0; 111 } 112 if(dcmp(C1.r + C2.r - d) < 0) return 0; //相離沒交點 113 if(dcmp(fabs(C1.r - C2.r) - d) > 0) return 0; //圓在圓中，沒有交點 114 115 double a = angle(C2.c - C1.c); //向量C1C2的極角 116 double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / (2 * C1.r * d)); //C1C2到C1P1的角 117 Point p1 = C1.point(a-da),p2 = C1.point(a+da); 118 119 sol.push_back(p1); 120 if(p1 == p2) return 1; //相切 121 sol.push_back(p2); 122 return 2; //相交 123 } 124 inline bool inside(double x,double y) 125 { 126 return (x>=0 && x<=1000 && y>=0 && y<=1000); 127 } 128 int main() 129 { 130 #ifndef ONLINE_JUDGE 131 freopen("test10.in","r",stdin); 132 // freopen("1.txt","w",stdout); 133 #endif 134 int i,j,k; 135 double x,y,z; 136 double xx,yy,zz; 137 // for(scanf("%d",&cass);cass;cass--) 138 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++) 139 // while(~scanf("%s",s)) 140 while(cin>>x>>y>>z) 141 { 142 cin>>xx>>yy>>zz>>k; 143 Circle c1(Point(x,y),z+zz),c2(Point(xx,yy),k); 144 145 if(dcmp(sqr(xx-x)+sqr(yy-y)-sqr(z+zz))>0) 146 { 147 puts("Yes"); 148 continue; 149 } 150 vector<Point>a; 151 vector<Point>::iterator iter; 152 while(!a.empty())a.pop_back(); 153 z=getCircleCircleIntersection(c1,c2,a); 154 if(z == -1) 155 { 156 puts("Yes"); 157 } 158 else if(z == 0) 159 { 160 double d = Length(c1.c - c2.c); 161 if(dcmp(d) == 0) //首先圓心要重合 162 { 163 if(dcmp(c1.r - c2.r) < 0)puts("Yes"); 164 else puts("No"); 165 } 166 else if(dcmp(c1.r + c2.r - d) < 0)puts("Yes");//相離沒交點 167 else if(dcmp(c2.r - c1.r - d) > 0)puts("Yes");//圓在圓中，沒有交點 168 else puts("No"); 169 } 170 else if(z == 1) 171 { 172 iter = a.begin(); 173 x = iter->x; 174 y = iter->y; 175 if(inside(x,y))puts("Yes"); 176 else puts("No"); 177 } 178 else 179 { 180 x=c1.c.x+(c2.c.x-c1.c.x)*c1.r/(Length(c1.c-c2.c)); 181 y=c1.c.y+(c2.c.y-c1.c.y)*c1.r/(Length(c1.c-c2.c)); 182 if(sqr(x-c2.c.x)+sqr(y-c2.c.y)<=k*k && inside(x,y)) 183 {puts("Yes");continue;} 184 185 iter = a.begin(); 186 x = iter->x; 187 y = iter->y; 188 iter++; 189 xx = iter->x; 190 yy = iter->y; 191 if(inside(x,y) || inside(xx,yy)) 192 puts("Yes"); 193 else puts("No"); 194 } 195 } 196 return 0; 197 } 198 /* 199 // 200 201 // 202 */ View Code

?

轉載于:https://www.cnblogs.com/Coolxxx/p/7065350.html

總結

以上是生活随笔為你收集整理的XMU 1071 圣斗士黄金十二宫（七）银河星爆 【计算几何】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。