1071.txt

厦门大学OJ上的ACM题1071目前最好算法

1071.圣斗士黄金十二宫（七）银河星爆
Time Limit: 1000 MS         Memory Limit: 65536 K 
Total Submissions: 411 (85 users)         Accepted: 27 (21 users) 
[ My Solution ] 

Description
　　撒加回答了星矢的第一个问题，但是当星矢要问第二个问题时，撒加的头发全变白了。白撒加的实力是无人能及的，星矢被废去了五感。这时帮沙加统计完单词的一辉也赶到了，想打赢白撒加是不可能的，一辉的目标就是争取时间让星矢拿到铜盾。为了尽快打倒被称为不死鸟的一辉，撒加也使出生平绝技---即使是星星被击中也要粉碎的银河星爆。
从撒加放出银河星爆到银河星爆接近一辉需要一段时间，在这段时间里一辉可以朝任何方向移动k单位的距离来躲开银河星爆。银河星爆的横截面为一个圆形，显然一辉在与横截面平行的平面上移动可以以最大的概率躲过。在该平面上建立直角坐标系横轴为x纵轴为y，银河星爆的横截面圆心坐标为(x1, y1)，半径为R1。
把一辉也当成一个圆，他在坐标系上朝任意方向移动的最大距离为k，考虑到地形因素和一辉个人能力，一辉所能移动到的点(x , y)需满足0 <= x <= 1000 , 0 <= y <= 1000。如果两个圆不相交则说明一辉躲过了银河星爆（注意两圆外切也说明一辉躲过了）。
现在请您预测一辉能否有可能躲过撒加的银河星爆。



Input
　　第一行为三个整数x1, y1, R1，代表银河星爆的圆心坐标和半径，其中0<= x1, y1 <= 1000, 0 < R1 <= 300。
第二行为三个整数x2, y2, R2，代表一辉的圆心坐标和半径，其中0 <= x2, y2 <= 1000, 0 < R2 <= 30。
第三行为一个正整数k <= 2000 表示一辉可以移动的最长距离。



Output
　　如果一辉可以躲过银河星爆则输出"Yes"，否则输出"No"（不包含引号）。



Sample Input
900 900 250
950 950 30
316



Sample Output
Yes







RunId 25351 of Problem 1071
Submit Time: 2008-10-16 19:03:15    Language: Gcc    Code Length: 1528 B 
Result: Accepted    Time: 4 MS    Memory: 40 K    Judge: Apple 

#include <stdio.h>   
#include <math.h>   
int main()   
{   
    int x1,y1,r1;   
    int x2,y2,r2;   
    int k;   
    double l;   
    double r;   
    double d;   
    scanf("%d %d %d", &x1, &y1, &r1);   
    scanf("%d %d %d", &x2, &y2, &r2);   
    scanf("%d", &k);   
    r = r1 + r2;   
    if (x1 < x2){   
        x1 = 1000 - x1;   
        x2 = 1000 - x2;   
    }   
    if (y1 < y2){   
        y1 = 1000 - y1;   
        y2 = 1000 - y2;   
    }   
    d = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));   
    if (x1*x1+y1*y1 < r*r){   
        double l1;   
        double l2;   
        double m1 = x1 - x2;   
        double m2 = sqrt(r*r-y1*y1);   
        double m = m1 + m2;   
        l1 = sqrt(y2*y2+m*m);   
        m1 = y1 - y2;   
        m2 = sqrt(r*r-x1*x1);   
        m = m1 + m2;   
        l2 = sqrt(x2*x2+m*m);   
        l = (l1<l2 ? l1 : l2);   
        if (k < l){   
            printf("No");   
            return 0;   
        }   
        else{   
            printf("Yes");   
            return 0;   
        }   
    }   
    if (x1 < r){   
        double y3 = (double)y1 - sqrt(r*r-x1*x1);   
        double y = (y1-y3)/x1*x2+y3;   
        if (y < y2){   
            double m1 = y1 - y2;   
            double m2 = sqrt(r*r-x1*x1);   
            double m3 = m2 - m1;   
            l = sqrt(m3*m3+x2*x2);   
            if (k < l){   
                printf("No");   
                return 0;   
            }   
            else{   
                printf("Yes");   
                return 0;   
            }   
        }   
    }   
    if (y1 < r){   
        double x3 = (double)x1 - sqrt(r*r-y1*y1);   
        double x = (x1-x3)/y1*y2+x3;   
        if (x < x2){   
            double m1 = x1 - x2;   
            double m2 = sqrt(r*r-y1*y1);   
            double m3 = m2 - m1;   
            l = sqrt(m3*m3+y2*y2);   
            if (k < l){   
                printf("No");   
                return 0;   
            }   
            else{   
                printf("Yes");   
                return 0;   
            }   
        }   
    }   
    if (d+k < r)   
        printf("No");   
    else  
        printf("Yes");   
    return 0;   
}