취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2415번 문제인 직사각형이다.
문제는 아래 링크를 확인하자.

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

어떤 (일치하지 않는) 두 선분이 직사각형의 마주보는 두 변일 필요충분조건 중 하나는 (1) 두 선분의 기울기가 같고 (2) 두 선분의 길이가 같고 (3) 두 선분의 양 끝점을 (교차하지 않게) 이어 얻을 수 있는 다른 두 선분이 기존 두 선분과 수직해야한다는 것이다. 따라서 위의 세 조건을 만족하게끔 모든 가능한 선분을 분류할 수 있다면 그 선분들 중 서로 가장 멀리 떨어진 두 선분으로 이루어진 직사각형을 모두 조사하는 것으로 문제를 해결할 수 있을 것이다.

어떤 선분이 잇는 두 점이 \((x_1,y_1)\)과 \((x_2,y_2)\)라 하자. 먼저 (1)과 (2)는 각 선분에 대하여 \(x_2-x_1\)과 \(y_2-y_1\)이 서로 같거나 두 값 모두 부호가 다를 경우 성립하며, 이는 필요충분조건이 된다. (3)은 원점을 지나며 주어진 선분과 수직한 다른 직선과 선분의 양끝점 사이의 부호 있는 거리(?)를 이용해 저장할 수 있다. 이는 점과 직선 사이의 거리 공식에 절댓값을 씌우지 않는 것으로 어렵지 않게 계산할 수 있으며, 이 때 분모는 (1)과 (2)를 저장하기 위한 값에 종속적이므로 이를 생략하여 저장하면 이 값 또한 정수로 관리할 수 있다. 이 세 값이 동일한 두 선분을 구성하는 네 점은 직사각형을 항상 구성할 수 있으므로, 이 3-tuple을 관리하는 것으로 문제를 해결할 수 있다.

위의 값이 같은 선분들에 대하여 이 선분과 평행하면서 원점을 지나는 직선 사이의 (부호 있는) 거리(?)의 최댓값과 최솟값을 관리하여 문제를 해결하자. 점과 직선 사이의 거리 공식의 분모에 들어가는 값이 선분의 길이와 같으므로, 분자만 저장해 나중에 분자의 최댓값에서 최솟값을 빼기만 하는 것으로 직사각형의 넓이를 얻을 수 있다!

위에서 "부호 있는 거리(?)"라고 언급한 값은 실제로는 방향이 있는 값이므로 거리는 아니지만 직관적인 설명을 위해 이렇게 서술하였다.

이와 같이 풀이하면 map을 쓰면서 대충 구현해도 예전 메모리제한(64MB)보다 적은 메모리를 사용해 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;

int N;
int P[1500][2];
ll ans;
map<pair<pair<ll, ll>, ll>, pair<ll, ll>> mp;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            ll dx = P[i][0] - P[j][0], dy = P[i][1] - P[j][1];
            if (!dx || dx * dy < 0) continue;
            dx = abs(dx), dy = abs(dy);
            ll D = min(dx * P[i][0] + dy * P[i][1], dx * P[j][0] + dy * P[j][1]), DD = dy * P[i][0] - dx * P[i][1];
            auto p = make_pair(make_pair(dx, dy), D);
            if (mp.count(p)) {
                auto &pp = mp[p];
                pp.first = max(pp.first, DD), pp.second = min(pp.second, DD);
            }
            else mp[p] = make_pair(DD, DD);
        }
    }

    for (auto &p:mp) ans = max(ans, p.second.first - p.second.second);
    cout << ans;
}

여담)

문제를 해결하고 나서 다른 사람들의 풀이를 보니 대체로 직사각형의 두 대각선은 중점과 길이는 같다는 성질을 이용해 중점과 길이가 같은 대각선 후보를 모으고 두 대각선을 골라 만들 수 있는 직사각형을 모두 조사하는 방식을 사용하고 있었다. 이와 같이 풀이하기 위해서는 중점과 길이가 같고 양끝점이 모두 정수 격자점인 선분이 많이 존재하지 않는다는 추가적인 관찰을 하거나 각도를 기준으로 하는 슬라이딩 윈도우를 적용하는 등의 추가적인 작업이 필요하다. 이와 같은 풀이의 아이디어나 구현, 그리고 최적화 등은 쉽지 않지만 알아둘 가치가 있는 풀이라고 생각해 같이 기록해 둔다.