Submission #242002


Source Code Expand

Copy
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

/**
 * Created by hama_du on 2014/09/27.
 */
public class Main {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        long a = in.nextLong();
        long b = in.nextLong();
        long A = Math.min(a, b);
        long B = a + b - A;

        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            long c = in.nextLong();
            long d = in.nextLong();
            if (place(A, B, c, d) || place(A, B, d, c) || place(B, A, c, d) || place(B, A, d, c)) {
                out.println("YES");
            } else {
                out.println("NO");
            }
        }
        out.flush();
    }

    private static boolean place(long A, long B, long c, long d) {
        if (((A <= c) && (B <= d)) || ((A <= d)) && (B <= c)) {
            return true;
        }

        // {ok,ng}
        double min1 = 0.0d;
        double max1 = A;
        for (int x = 0 ; x < 40 ; x++) {
            double med = (min1 + max1) / 2;
            if (isok1(A, B, c, d, med)) {
                min1 = med;
            } else {
                max1 = med;
            }
        }

        // {ng,ok}
        double min2 = 0.0d;
        double max2 = A;
        for (int x = 0 ; x < 40 ; x++) {
            double med = (min2 + max2) / 2;
            if (isok2(A, B, c, d, med)) {
                max2 = med;
            } else {
                min2 = med;
            }
        }
        return (max2 < min1);
    }

    public static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }


    private static boolean isok1(long a, long b, long c, long d, double X) {
        double Y = Math.sqrt(a * a - X * X);
        double da = Y + b * X / a;
        if (da > d) {
            return false;
        }
        return true;
    }

    private static boolean isok2(long a, long b, long c, long d, double X) {
        double Y = Math.sqrt(a * a - X * X);
        double xy = Math.sqrt(X * X + Y * Y);
        double db = X + b * Y / xy;
        if (db > c) {
            return false;
        }
        return true;
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}

Submission Info

Submission Time
Task B - 高橋君と禁断の書
User hamadu
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 4709 Byte
Status
Exec Time 453 ms
Memory 22576 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0-sample-01.txt
All 100 / 100 subtask0-sample-01.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt
Case Name Status Exec Time Memory
subtask0-sample-01.txt 334 ms 20640 KB
subtask1-01.txt 334 ms 20608 KB
subtask1-02.txt 354 ms 21564 KB
subtask1-03.txt 401 ms 22008 KB
subtask1-04.txt 379 ms 22020 KB
subtask1-05.txt 371 ms 21892 KB
subtask1-06.txt 377 ms 21888 KB
subtask1-07.txt 365 ms 21944 KB
subtask1-08.txt 380 ms 21816 KB
subtask1-09.txt 380 ms 21940 KB
subtask1-10.txt 411 ms 22012 KB
subtask1-11.txt 387 ms 22016 KB
subtask1-12.txt 384 ms 22576 KB
subtask1-13.txt 386 ms 22004 KB
subtask1-14.txt 384 ms 22008 KB
subtask1-15.txt 385 ms 22024 KB
subtask1-16.txt 401 ms 22008 KB
subtask1-17.txt 387 ms 22016 KB
subtask1-18.txt 393 ms 22072 KB
subtask1-19.txt 383 ms 22016 KB
subtask1-20.txt 395 ms 22012 KB
subtask1-21.txt 414 ms 22208 KB
subtask1-22.txt 410 ms 22044 KB
subtask1-23.txt 388 ms 21996 KB
subtask1-24.txt 453 ms 22096 KB
subtask1-25.txt 414 ms 22016 KB
subtask1-26.txt 394 ms 21960 KB
subtask1-27.txt 377 ms 21884 KB
subtask1-28.txt 418 ms 22040 KB
subtask1-29.txt 419 ms 22052 KB
subtask1-30.txt 427 ms 21964 KB