随笔 - 9, 文章 - 0, 评论 - 1, 引用 - 0
数据加载中……

2009年8月28日

PKU 3747 Scout YYF II

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();
    }

}


posted @ 2009-08-31 21:57 yessit 阅读(188) | 评论 (0) | 编辑 收藏

PKU 3742 Equivalent Polynomial

http://acm.pku.edu.cn/JudgeOnline/problem?id=3742

高精度加法和乘法.
复杂度: O(aN2)(a为高精度的代价)

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

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

public class Main {

    private static final int        MAX_N = 200;

    private static BufferedReader   in =
            new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer  st;
    private static BigInteger[][]   C = new BigInteger[MAX_N + 1][];
    private static BigInteger[]     a = new BigInteger[MAX_N + 1];
    private static BigInteger[]     pow = new BigInteger[MAX_N + 1];

    public static void main(String[] argv) throws Exception {
        int         N, t, signalt, signal;
        int         i, j;
        BigInteger  T, x;
        initialize();
        while (in.ready()) {
            N = nextInt();
            t = nextInt();
            if (t < 0) {
                t = -t;
                signalt = 1;
            } else signalt = -1;
            T = BigInteger.valueOf(t);
            pow[0] = BigInteger.ONE;
            for (i = 1; i <= N; i++) pow[i] = pow[i - 1].multiply(T);
            for (i = 0; i <= N; i++)
                a[i] = BigInteger.valueOf(nextInt());
            for (i = N; i >= 0; i--) {
                for (signal = signalt, j = i - 1; j >= 0; j--, signal *= signalt) {
                    x = a[i].multiply(C[i][j]).multiply(pow[i - j]);
                    if (signal < 0) a[j] = a[j].subtract(x.negate());
                    else a[j] = a[j].subtract(x);
                }
            }
            for (i = 0; i <= N; i++) {
                if (i != 0) System.out.print(" ");
                System.out.print(a[i]);
            }
            System.out.println();
        }
    }

    private static void initialize() {
        int i, j;
        C[0] = new BigInteger[1];
        C[0][0] = BigInteger.ONE;
        for (i = 1; i <= MAX_N; i++) {
            C[i] = new BigInteger[i + 1];
            C[i][0] = C[i][i] = BigInteger.ONE;
            for (j = 1; j < i; j++)
                C[i][j] = C[i - 1][j - 1].add(C[i - 1][j]);
        }
    }

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

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

}


posted @ 2009-08-28 23:48 yessit 阅读(165) | 评论 (0) | 编辑 收藏

PKU 3744 Scout YYF I

http://acm.pku.edu.cn/JudgeOnline/problem?id=3744

从题意可以得出递推式: PN = p * PN - 1 + (1 - p) * PN - 2;
可导出通项公式: PN = Pstart / (p - 2) * ((p - 1) N + 1 - 1)
之后就可以直接套用公式了.

/**
 * @version 2009/08/28
 * @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;

    public static void main(String[] argv) throws Exception {
        int[]   list = new int[10];
        int     i, temp, last;
        int     N;
        double  p, val;
        boolean found;
        while (true) {
            N = nextInt();
            p = nextDouble();
            for (i = 0; i < N; i++) list[i] = nextInt();
            Arrays.sort(list, 0, N);
            for (temp = N, N = i = 1; i < temp; i++)
                if (list[i] != list[i - 1]) list[N++] = list[i];
            for (found = false, i = 0; !found && i < N; i++)
                if (list[i] == 1 || i > 0 && list[i] == list[i - 1] + 1)
                    found = true;
            if (found) {
                System.out.println("0.0000000");
                continue;
            }
            last = 1;
            val = 1.0;
            for (i = 0; i < N; i++) {
                val = val * (Math.pow(p - 1, list[i] - last) - 1.0) / (p - 2.0) * (1 - p);
                last = list[i] + 1;
            }
            System.out.format("%.7f%n", val);
        }
    }

    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();
    }

}


posted @ 2009-08-28 21:43 yessit 阅读(200) | 评论 (0) | 编辑 收藏

PKU 3740 Easy Finding

http://acm.pku.edu.cn/JudgeOnline/problem?id=3740

按照题目条件暴力枚举.
复杂度: O(2NM)
/**
 * @version 2009/08/28
 * @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 int[]            matrix = new int[300];

    public static void main(String[] argv) throws Exception {
        int     N, M;
        int     i, j, x;
        boolean found;
        while (in.ready()) {
            N = nextInt();
            M = nextInt();
            Arrays.fill(matrix, 0);
            for (i = 0; i < N; i++)
                for (j = 0; j < M; j++)
                    if (nextInt() == 1)
                        matrix[j] |= 1 << i;
            for (found = false, i = (1 << N) - 1; !found && i >= 0; i--) {
                for (j = 0; j < M; j++) {
                    x = i & matrix[j];
                    if (x == 0 || x - (x & (-x)) != 0) break;
                }
                if (j == M) {
                    found = true;
                    System.out.println("Yes, I found it");
                }
            }
            if (!found) System.out.println("It is impossible");
        }
    }

    private static int nextInt() throws Exception {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return Integer.parseInt(st.nextToken());
    }

}


posted @ 2009-08-28 20:55 yessit 阅读(415) | 评论 (1) | 编辑 收藏