[자바] 백준 13552 - 구와 쿼리 (boj java)

문제 : boj13552

 

  처음엔 시간 제한을 안보고 다음과 같이 생각했다. x,y,z값을 sqrt(1000000)정도씩 구간을 나눠서 연산을 줄이면 어찌저찌 되지 않을까 싶었다.

 

  하지만, 시간 제한을 보니 출제 의도가 그냥 한번 해보라는 것 같았다. 모든 경우를 살펴본다고 하면, O(NM)으로 사실 무리가 있을 것 같긴 했는데, 시간 제한이 20초나 되므로 일단 해보기로 했다(자바의 경우 주어진 시간 x2+1초 이므로 총 41초 제한이다.). 그래도 만만치 않은 수치이므로 입출력 모두 빠르게 되도록 짰고, 연산이 느리고 불명확해서 틀릴 가능성이 있는 double을 사용하지 않도록 짰다.

 

  참고로 3차원에서 두 점 (a,b,c), (x,y,z)의 거리는 (A)와 같이 구할 수 있다. 이 문제에서는 반지름이 r인 구 내부의 점을 구해야 하므로, (B)를 만족하는 (a,b,c)의 개수를 세야 한다. 이 때 double을 사용하지 않고 풀려면 양변을 제곱해서 (C)와 같은 수식으로 풀면 된다.

 

코드 : github

import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;

public class Main extends FastInput {
    private long getPowOfDistance(int[] point, int x, int y, int z){
        int a = point[0]-x;
        int b = point[1]-y;
        int c = point[2]-z;
        return 1l*a*a+1l*b*b+1l*c*c;
    }
    private void solution() throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = nextInt();
        int[][] arr = new int[n][3];
        for (int i = 0; i < n; i++) {
            arr[i][0] = nextInt();
            arr[i][1] = nextInt();
            arr[i][2] = nextInt();
        }
        int m = nextInt();
        StringBuilder sb = new StringBuilder();
        while (m-->0) {
            int x = nextInt();
            int y = nextInt();
            int z = nextInt();
            int r = nextInt();
            long rPow = 1l*r*r;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (getPowOfDistance(arr[i], x, y, z) <= rPow) cnt++;
            }
            sb.append(cnt).append('\n');
        }
        bw.write(sb.toString());
        bw.flush();
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}