http://acm.pku.edu.cn/JudgeOnline/problem?id=3747
题目中爆炸的扩大速度与人的逃走速度是一致, 这就决定了逃走的最佳路线一定是一条直线, 而且这样使得长度与时间的比较等价, 这个是这道题目的关键.
若假设YYF的逃出点为C, YYF的起点为A, 爆炸发生点为B, 那么一定有AC > AB.
所以对于一个爆炸点来说AB中垂线划分出的A所在一边为安全区域. 接下来的就是经典的圆周覆盖问题了.
复杂度: O(N)
/**
* @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();
}
}