首页 > 代码库 > URAL 1913 Titan Ruins: Old Generators Are Fine Too
URAL 1913 Titan Ruins: Old Generators Are Fine Too
不知道怎么就1A了。。题目意思不难理解,设水晶的坐标为s0,两个发动机的坐标是s1,s2,半径为R,就分三种情况。。第一种情况就是s1,s2到s0的距离都小于2*R,这种情况,两个人的位置就是s1-s0,s2-s0的中点;第二种情况就是s1和s2只有一个到s0的距离小于2*R,假设s1相交,这个时候s1与s0相交的交点,两个交点所在的圆弧里面就是其中一个人的坐标,另外一个人的坐标有可能在两个交点上,也有可能在圆弧里面;第三种情况就是s1和s2到s0的距离大于2*R,但是s1和s2的距离小于2*R,这个时候其中一个人的坐标就是在s1和s2交点所在的圆弧里面,另一个人的坐标根据s0到s1,s2还有圆弧交点来判断;最后一种情况就是以上三种都不满足,就输出death。。具体还是看代码,然后画一画,就明白了。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <map> 7 8 using namespace std; 9 10 #define LL long long 11 #define eps 1e-10 12 #define mxn 1000200 13 #define mxe 2000020 14 #define inf 1e12 15 #define Pi acos( -1.0 ) 16 17 //精度 18 int dcmp( double x ){ 19 if( fabs( x ) < eps ) return 0; 20 return x < 0 ? -1 : 1; 21 } 22 // 点 23 struct point{ 24 double x, y; 25 point( double x = 0, double y = 0 ) : x(x), y(y) {} 26 point operator + ( const point &b ) const{ 27 return point( x + b.x, y + b.y ); 28 } 29 point operator - ( const point &b ) const{ 30 return point( x - b.x, y - b.y ); 31 } 32 point operator * ( const double &k ) const{ 33 return point( x * k, y * k ); 34 } 35 point operator / ( const double &k ) const{ 36 return point( x / k, y / k ); 37 } 38 bool operator < ( const point &b ) const{ 39 return dcmp( x - b.x ) < 0 || dcmp( x - b.x ) == 0 && dcmp( y - b.y ) < 0; 40 } 41 bool operator == ( const point &b ) const{ 42 return dcmp( x - b.x ) == 0 && dcmp( y - b.y ) == 0; 43 } 44 double len(){ 45 return sqrt( x * x + y * y ); 46 } 47 }; 48 typedef point Vector; 49 // 点积 50 double dot( Vector a, Vector b ){ 51 return a.x * b.x + a.y * b.y; 52 } 53 // 叉积 54 double cross( Vector a, Vector b ){ 55 return a.x * b.y - a.y * b.x; 56 } 57 //两圆相交 58 void circle_cross( point a, double ra, point b, double rb, point &v1, point &v2 ){ 59 double d = ( a - b ).len(); 60 double da = ( ra * ra + d * d - rb * rb ) / ( 2 * ra * d ); 61 double aa = atan2( (b-a).y, (b-a).x ); 62 double rad = acos( da ); 63 v1 = point( a.x + cos( aa - rad ) * ra, a.y + sin( aa - rad ) * ra ); 64 v2 = point( a.x + cos( aa + rad ) * ra, a.y + sin( aa + rad ) * ra ); 65 } 66 double R; 67 point s0, s1, s2; 68 void solve(){ 69 point ans1, ans2; 70 if( dcmp( (s0-s1).len() - 2 * R ) <= 0 && dcmp( (s0-s2).len() - 2 * R ) <= 0 ){ 71 ans1 = (s0+s1)/2, ans2 = (s0+s2)/2; 72 } 73 else if(dcmp( (s0-s1).len() - 2 * R ) <= 0 || dcmp( (s0-s2).len() - 2 * R ) <= 0){ 74 if( dcmp( (s0-s2).len() - 2 * R ) <= 0 ) swap( s1, s2 ); 75 point v1, v2; 76 double tmp; 77 circle_cross( s0, R, s1, R, v1, v2 ); //v1,v2扇形交点 78 tmp = (s2-v1).len(), ans1 = v1, ans2 = (s2+v1)/2; 79 if( (s2-v2).len() < tmp ) 80 tmp = (s2-v2).len(), ans1 = v2, ans2 = (s2+v2)/2; 81 double len1 = (s2-s0).len(), len2 = (s2-s1).len(); 82 point u1 = s0 + ( s2 - s0 ) * (R/len1); 83 if( (u1-s1).len() <= R ){ 84 if( (s2-u1).len() < tmp ) 85 tmp = (s2-u1).len(), ans1 = u1, ans2 = (s2+u1)/2; 86 } 87 point u2 = s1 + ( s2 - s1 ) * (R/len2); 88 if( (u2-s0).len() <= R ){ 89 if( (s2-u2).len() < tmp ) 90 tmp = (s2-u2).len(), ans1 = u2, ans2 = (s2+u2)/2; 91 } 92 if( tmp > 2 * R ){ 93 puts( "Death" ); return ; 94 } 95 } 96 else{ 97 if( dcmp( (s1-s2).len() - 2 * R ) > 0 ){ 98 puts( "Death" );return ; 99 }100 point v1, v2;101 circle_cross( s1, R, s2, R, v1, v2 );102 double tmp;103 tmp = (s0-v1).len(), ans1 = v1, ans2 = (s0+v1)/2;104 if( (s0-v2).len() < tmp )105 tmp = (s0-v2).len(), ans1 = v2, ans2 = (s0+v2)/2;106 double len1 = (s0-s1).len(), len2 = (s0-s2).len();107 point u1 = s1 + (s0-s1) * (R/len1), u2 = s2 + (s0-s2)* (R/len2);108 if( (u1-s2).len() <= R ){109 if( (s0-u1).len() < tmp )110 tmp = (s0-u1).len(), ans1 = u1, ans2 = (u1+s0)/2;111 }112 if( (u2-s1).len() <= R ){113 if( (s0-u2).len() < tmp ){114 tmp = (s0-u2).len(), ans1 = u2, ans2 = (u2+s0)/2;115 }116 }117 if( tmp > 2 * R ){118 puts( "Death" ); return;119 }120 }121 puts( "Now we have enough power");122 printf( "%.5lf %.5lf\n%.5lf %.5lf\n", ans1.x, ans1.y, ans2.x, ans2.y );123 }124 int main(){125 scanf( "%lf", &R );126 scanf( "%lf %lf", &s0.x, &s0.y );127 scanf( "%lf %lf", &s1.x, &s1.y );128 scanf( "%lf %lf", &s2.x, &s2.y );129 solve();130 return 0;131 }
URAL 1913 Titan Ruins: Old Generators Are Fine Too
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。