2261번 가장 가까운 두 점

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

이 글의 코드는 아래의 글을 참고하여 작성한 코드입니다.

아래의 글을 보시길 추천합니다.

https://www.acmicpc.net/blog/view/25

또한, set은 기본적으로 first를 기준으로 오름차순 정렬 후에 second를 정렬되어 있다.

그러나 필요한 것은 second(y)를 기준으로 한 것이 필요하기 때문에 정렬 구조체(ordery)를  추가해야한다.

#include<bits/stdc++.h>
 
using namespace std;
 
int n;
vector<pair<int, int> > v;
 
struct ordery
{
    bool operator() (const pair<int, int> &a, const  pair<int, int> &b) const
    {
        if (a.second == b.second) {
            return a.first < b.first;
        }
        else {
            return a.second < b.second;
        }
    }
};
 
int dist(pair<int, int> a, pair<int, int> b)
{
    return (a.first - b.first)*(a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        v.push_back({ x, y });
    }
 
    // x(first) 기준으로 오름차순. 그 후 y(second) 기준으로 오름차순
    sort(v.begin(), v.end());
 
    // 가장 가까운 두 점의 후보를 candidate에 넣는다. v[0]과 v[1]
    // 참고로 y(second) 기준으로 오름차순해야 한다.
    // y를 기준으로 이분 탐색을 실행할 예정
    set<pair<int, int>, ordery> candidate = { v[0], v[1] };
 
    /*
    그 두 점 사이의 거리를 구한다.
    즉, 여기까지만 봤을 때 가장 가까운 두 점은 v[0], v[1]이고, 그 거리는 ans라고 '가정'한 것이다.
    */
    int ans = dist(v[0], v[1]);
    int Start = 0;
 
    // v[0]과 v[1]은 위에서 구했다.
    for (int i = 2; i < n; i++) {
 
        // 현재 좌표
        pair<int, int> now = v[i];
 
        while (Start < i)
        {
            auto p = v[Start];
 
            int x = now.first - p.first;
 
            if (x*x > ans) {
                candidate.erase(p);
                ++Start;
            }
            else {
                break;
            }
        }
 
        /*
        ans에는 거리의 제곱이 저장되어 있기 때문에, 제곱근을 구해야 한다.
        */
        int d = (int)sqrt(double(ans)) + 1;
        auto lower_point = pair<int, int>(-100000, now.second - d);
        auto upper_point = pair<int, int>(100000, now.second + d);
        /*
        x좌표에는 -100,000을 넣는 이유는 같은 y좌표를 가지는 점이 여러 개일 때, 
        가능한 x 좌표의 값 중 가장 작은 값(-10,000)보다 작기 때문
        */
 
        auto lower = candidate.lower_bound(lower_point);
        auto upper = candidate.upper_bound(upper_point);
 
        for (auto it = lower; it != upper; it++) {
            int temp_dist = dist(now, *it);
            if (temp_dist < ans) {
                ans = temp_dist;
            }
        }
 
        candidate.insert(now);
    }
 
    printf("%d\n", ans);
 
    return 0;
}