首页 > 代码库 > 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 }
View Code

 

URAL 1913 Titan Ruins: Old Generators Are Fine Too