글 읽기 - 2261번 97%에서 틀렸습니다....

alreadyj 6년 전 0

97%에서 틀렸습니다가 뜨네요... 반례가 있는걸까요?

현재 점을 중심으로 거리가 root(min) + 1인 정사각형 안에 있는 점들에 대해서 min값을 계산 하는 방식인데,

정말 모르겠네요.

import java.util.Scanner;

public class Main {
    static int N, x, y, min = 400000004;
    static Point[] points;
    static boolean[][] table = new boolean[20002][20002];
    static boolean[] X = new boolean[20002];
    static boolean isSamePoint = false;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();points = new Point[N];
        for (int i = 0; i < N; i++) {
            x = sc.nextInt(); y = sc.nextInt();
            points[i] = new Point(x + 10000, y + 10000);
            //모든 좌표를 1사분면으로 옮김
            if (table[x + 10000][y + 10000])
                isSamePoint = true;//만약 같은 좌표가 있다면 0을 출력하기 위한 flag
            table[x + 10000][y + 10000] = true;X[x + 10000] = true;
            //2차원 배열에 각좌표를 표시, X 좌표만 표시
        }
        if (!isSamePoint) {
            for (int i = 0; i < N; i++) {//모든 좌표에 대하여
                Point c = points[i];
                int upper = Math.min(c.x + (int) Math.sqrt(min) + 1, 20002);
                int lower = Math.max(c.x - (int) Math.sqrt(min) - 1, 0);
                int up = Math.min(c.y + (int) Math.sqrt(min) + 1, 20002);
                int low = Math.max(c.y - (int) Math.sqrt(min) - 1, 0);
                //현재 좌표를 중심으로 거리가 root(min)인 정사각형 안에서 탐색 시작.
                for (int j = lower; j < upper; j++) {
                    if (X[j]) {//x가 있는 좌표이면
                        for (int k = low; k < up; k++) {
                            // 현재 좌표와 같은 곳은 제외하고 모든 좌표와 비교를 함.
                            if (table[j][k] && !(c.x == j && c.y == k)) {
                                min = Math.min(min, (int) (Math.pow(c.x - j, 2) + Math.pow(c.y - k, 2)));
                            }
                        }
                    }
                }
            }
            System.out.println(min);
        }else System.out.println(0);
    }
    private static class Point {
        int x, y;
        Point(int x, int y) {
            this.x = x;this.y = y;
        }
    }
}