[BaekJoon] 9015 정사각형 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/9015

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();

    static int N;
    static int answer;
    static Set<Point> pointsSet;
    static Point[] points;

    static void input() {
        N = scanner.nextInt();
        answer = 0;
        pointsSet = new HashSet<>();
        points = new Point[N];

        for(int idx = 0; idx < N; idx++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();

            points[idx] = new Point(x, y);
            pointsSet.add(new Point(x, y));
        }
    }

    static void solution() {
        for(int point1Idx = 0; point1Idx < N; point1Idx++) {
            for(int point2Idx = 0; point2Idx < N; point2Idx++) {
                if(point1Idx == point2Idx) {
                    continue;
                }

                Point point1 = points[point1Idx];
                Point point2 = points[point2Idx];
                int xGap = point1.x - point2.x;
                int yGap = point1.y - point2.y;
                if(answer >= (Math.pow(xGap, 2) + Math.pow(yGap, 2))) {
                    continue;
                }

                if(pointsSet.contains(new Point(point1.x - yGap, point1.y + xGap)) &&
                        pointsSet.contains(new Point(point2.x - yGap, point2.y + xGap))) {
                    answer = Math.max(answer, (int)Math.pow(xGap, 2) + (int)Math.pow(yGap, 2));
                }
            }
        }

        sb.append(answer).append('\n');
    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        while(T-- > 0) {
            input();
            solution();
        }

        System.out.print(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 정사각형에서 두 점을 알고있는 상황에서 다른 두 점을 구할 수 있다.
• 그러므로 주어진 N개의 점을 2개씩 묶어서 그 두 점을 정사각형의 두 점이라고 생각하고, 나머지 두 점을 구하여 그 점들이 N개의 점 중에 존재하는지 판단한다.
  • 만약 존재한다면 묶은 두 점을 통해 정사각형이 만들어진다는 뜻이므로, 그 정사각형의 넓이를 구하여 최댓값을 갱신한다.

정사각형 두 점을 알고 있는 상황에서 다른 두 점은?

• $(x_1, y_1), (x_2, y_2)$가 정사각형의 두 점이라고 생각했을 때, 우리가 구해야 할 두 점은 $(x_3, y_3), (x_4, y_4)$이다.
• 빨간색 정사각형 외부에 보이는 4개의 삼각형은 모두 합동이다.
• 그러므로 위 그림과 같이 $(x_1, y_1)$부터의 xGap과 $(x_2, y_2)$부터의 yGap은 각각 $(x_2, y_2)$부터의 xGap과 $(x_3, y_3)$부터의 yGap은 같다.
• 이에 따라 $(x_3, y_3), (x_4, y_4)$ 두 점은 아래와 같이 나타낼 수 있다.
  • $(x_3, y_3)$ = $(x_2 - yGap , y_2 + xGap)$
  • $(x_4, y_4)$ = $(x_1 - yGap , y_1 + xGap)$