BOJ 9015 - 정사각형 [C++]

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

9015번: 정사각형

문제 요약

평면 위에 $N$개의 점이 주어졌을 때, 가장 큰 정사각형의 넓이를 구하는 문제이다.

 

문제 해결

어떠한 두 점 $P, Q$를 골랐을 때, 그 두 점을 이은 선분을 변으로 갖는 정사각형이 있는지 알 수 있을까?

 

그 두 점의 $x$좌표 변화량과 $y$좌표 변화량을 각각 $dx, dy$라고 하자.

$P, Q$를 $(dx, -dy)$만큼 대칭이동한 점이 둘 다 존재한다면 정사각형이 된다.

이렇게 만들어진 사각형은 모두 변의 길이가 같고, 네 각이 항상 직각이 되기 때문에 정사각형이다.

 

점의 존재여부를 set으로 관리하면 전체 시간복잡도는 $O(N^2\log{N})$이다.

 

코드

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int T;
    for (cin >> T; T--;) {
        int N;
        cin >> N;
        vector<ii> arr(N);
        set<ii> S;
        for (int i = 0; i < N; i++) {
            int a, b;
            cin >> a >> b;
            arr[i] = make_pair(a, b);
            S.insert(arr[i]);
        }
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int dx = arr[i].first - arr[j].first;
                int dy = arr[i].second - arr[j].second;
                ii p1 = make_pair(arr[i].first - dy, arr[i].second + dx);
                ii p2 = make_pair(arr[j].first - dy, arr[j].second + dx);

                if (S.count(p1) && S.count(p2)) {
                    ans = max(ans, dx * dx + dy * dy);
                }
            }
        }
        cout << ans << '\n';

    }

}