首页 > 专题系列 > Java解POJ > POJ 3747 Scout YYF II [解题报告] Java
2013
11-13

POJ 3747 Scout YYF II [解题报告] Java

Scout YYF II

问题描述 :

After the dangerous “mine road”, YYF has finally enter the enemy’s base, which is a round glass building. However, this is totally a trap! There are no enemy in the base but bombs instead. Some time after YYF enter the base, the enemy’s detectors find him and ignite the bomb system to kill him. As a professional scout, YYF feels the bomb and choose a best direction to run. When a bomb explodes, it will destroy a circle area including the boundary which becomes larger and larger. YYF runs very fast in the same speed as the radius of bomb area grows. If he can run out of the base before the explosions destroy him, he will be safe after that. Now you are given the YYF’s and bombs’ initial places, please calculate that if our couragous scout can possibly save himself.

输入:

The input contains many test cases ended with EOF.
The first line of each test case is N (1 ≤ N ≤ 10) and R (1 ≤ R ≤ 1000), standing for the number of bombs and the radius of the base. The center of the base is always at (0,0). The second line of each test case is two real numbers standing for the initial place of YYF.
In the next N lines, each contains two real numbers standing for the initial place of a bomb.
It is guaranteed that all the initial places is in the base.

输出:

For each test case, if YYF can escape safely, output “Yes” in a single line, otherwise “No” instead.

样例输入:

2 10
0 0
1 0
-1 0
4 10
0 0
1 0
-1 0
0 1
0 -1

样例输出:

Yes
No

解题代码:

//* @author 
/**
 * @version 2009/08/31
 * @author sbzlyessit
 */

import java.io.*;
import java.util.*;

public class Main {

    private static BufferedReader   in =new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer  st;
    private static double[] x = new double[10], y = new double[10];
    private static double[] d = new double[20];
    private static double   x0, y0;
    private static int      N;
    private static double   R;

    public static void main(String[] argv) throws Exception {
        while (in.ready()) {
            N = nextInt();
            R = nextDouble();
            x0 = nextDouble();
            y0 = nextDouble();
            for (int i = 0; i < N; i++) {
                x[i] = nextDouble();
                y[i] = nextDouble();
            }
            solve();
        }
    }

    private static void solve() {
        double  a, b, c, delta, t1, t2, a0, a1, b0, b1, x1, y1;
        for (int i = 0; i < N; i++) {
            if (doubleCmp(x[i], x0) == 0 && doubleCmp(y[i], y0) == 0) {
                System.out.println("No");
                return;
            }
            a0 = x[i] - x0;
            b0 = y[i] - y0;
            x1 = x0 + a0 / 2;
            y1 = y0 + b0 / 2;
            a1 = -b0;
            b1 = a0;
            a = sqr(a1) + sqr(b1);
            b = 2 * a1 * x1 + 2 * b1 * y1;
            c = sqr(x1) + sqr(y1) - sqr(R);
            delta = Math.sqrt(sqr(b) - 4 * a * c);
            t1 = (-b + delta) / 2 / a;
            t2 = (-b - delta) / 2 / a;
            d[2 * i] = Math.atan2(y1 + t1 * b1, x1 + t1 * a1);
            d[2 * i + 1] = Math.atan2(y1 + t2 * b1, x1 + t2 * a1);
        }
        Arrays.sort(d, 0, 2 * N);
        for (int i = 0; i < 2 * N; i++)
            if (check(d[i], d[(i + 1) % (2 * N)])) {
                System.out.println("Yes");
                return;
            }
        System.out.println("No");
    }

    private static boolean check(double xt, double yt) {
        if (yt < xt) yt += 2 * Math.PI;
        xt = (xt + yt) / 2;
        yt = R * Math.sin(xt);
        xt = R * Math.cos(xt);
        for (int i = 0; i < N; i++)
            if (doubleCmp(dist(x[i], y[i], xt, yt), dist(x0, y0, xt, yt)) < 0) return false;
        return true;
    }

    private static double dist(double x1, double y1, double x2, double y2) {
        return Math.sqrt(sqr(x1 - x2) + sqr(y1 - y2));
    }

    private static int doubleCmp(double a, double b) {
        if (Math.abs(a - b) < 1e-6) return 0;
        return a < b ? -1 : 1;
    }

    private static double sqr(double x) {
        return x * x;
    }

    private static int nextInt() throws Exception {
        return Integer.parseInt(next());
    }

    private static double nextDouble() throws Exception {
        return Double.parseDouble(next());
    }

    private static String next() throws Exception {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }

}

  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?