[C/C++] 백준 2261번 - 가장 가까운 두 점 (라인 스위핑)

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

#define INF (1 << 30)
#define X first
#define Y second
typedef pair<int, int> pi;

int n, x, y;
vector<pi> v;
set<pi> s;

int dist(pi a, pi b) 
{
    int x_dist = (a.X - b.X) * (a.X - b.X);
    int y_dist = (a.Y - b.Y) * (a.Y - b.Y);
    return x_dist + y_dist;
}

int main() {

    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        cin >> x >> y;
        v.push_back({ x,y });
    }

    // X좌표 순으로 정렬
    sort(v.begin(), v.end());
    s.insert({ v[0].Y, v[0].X });
    s.insert({ v[1].Y, v[1].X });

    int mini = dist(v[0], v[1]);
    int idx = 0;

    for (int i = 2; i < n; ++i)
    {
        while (idx < i)
        {
            int d = v[i].X - v[idx].X;
            if (d * d <= mini) break;
            else // mini보다 거리가 멀 시 후보군에서 제외
            {
                s.erase({ v[idx].Y, v[idx].X });
                idx++;
            }
        }

        // 후보군 내의 점들과의 거리 중 가장 가까운 거리로 업데이트
        auto start = s.lower_bound({ v[i].Y - sqrt(mini), -INF });
        auto end = s.upper_bound({ v[i].Y + sqrt(mini), INF });
        for (auto it = start; it != end; it++)
            mini = min(mini, dist({ it->Y, it->X }, v[i]));
        s.insert({ v[i].Y, v[i].X });
    }
    
    cout << mini << '\n';
}

set container를 이용하는 이유 : BST(균형 이진트리)로 이루어져 있으며, 원소가 자동 정렬되고 중복되는 값을 제거해주는 기능이 있기 때문에 set을 사용하였습니다.

 

 

풀이 방법

 

점 개수가 최대 10만개이므로 O(N²)의 시간 복잡도로는 시간 초과가 발생하기 때문에 라인 스위핑 알고리즘으로 풀이를 하였습니다.

 

<알고리즘>

1) 벡터를 X좌표 순으로 정렬을 한 뒤 첫번째 점과 두 번째 점을 set에 insert 한다.

2) 첫번째 점과 두 번째 점 사이의 거리를 변수 mini의 초기값으로 지정한다

3) i번째 점과 비교했을때 X좌표 사이의 거리가 mini보다 크다면 후보군에서 제외한다.

4) 후보군 내의 점들과의 거리들 중에서 가까운 거리로 mini를 업데이트한다.

 

 

 

 

 

www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점