[C++] 2261번 가장 가까운 두 점 - 기하학, 스위핑, 분할 정복

나는 스위핑으로 풀었다. 분할 정복 풀이를 원하는 사람은 다른 블로그로 -> ->

 

1. 문제

• 2차원 평면 상에 n개의 점이 주어져 있을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.
• \(n(2 \leq n \leq 100,000)\)
• \(\left|x \right|, \left|y \right| \leq 10000, x, y \in \mathbb{Z} \)

<입력>

• 각 점의 x, y 좌표가 주어짐

<출력>

• 가장 가까운 두 점의 거리의 제곱을 출력

2. 재정의

• n개의 점들 중 가장 가까운 두 점 사이 거리 구하기

3. 해결 방법

1. Vertex.push_back({x, y})
2. 좌표들을 x축을 기준으로 오름차순 정렬하기
3. 제일 왼쪽 부터 차례대로 점들을 확인하며 스위핑을 수행
4. <x축> set container에는 고려해야 할 점들이 x축 정렬되어 있는데 dist(set container 위 점, 탐색할 점)^2 >= mindist일 경우 더 이상 고려할 필요가 없기 때문에 제외
5. x축상에서 가능한 점들 중 y축상으로 sqrt(mindist)이하로 차이나는 점들 중 거리를 계산해 최솟값인 minDist를 갱신하기
6. 탐색한 좌표를 set container에 넣어줌
7. (항상 탐색한 점은 왼쪽 점들만 탐색하므로 오른쪽 점들은 상관할 필요가 없음)

4. 실수한 점, 개선할 점

• 주소값은 크기 비교가 불가하며 같다, 다르다만 판단할 수 있다.
• set container에서 upper_bound랑 lower_bound로 pair<int, int>값을 찾아줄 때 항상 첫 번째 값을 먼저 검색한 후 그중 두 번째 값과 제일 가까운 값의 주소를 반환한다. 그래서 둘을 반대로 적어 set에는 첫 번째 값이 Y, Vertex에는 X가 들어가 헷갈릴 수 있다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>

#define pii pair<int, int>

#define X first
#define Y second

using namespace std;

const int INF = 987654321;
const int MAX_N = 100001;

int n;
//x, y 좌표
vector<pii> Vertex;
//고려해야할 점들이 들어있는 set container
set<pii> s;
//두 점 사이의 최소 서리
int minDist;

void input()
{
    cin >> n;
    for(int i=0; i<n; i++) {
        int x, y;
        
        cin >> x >> y;
        Vertex.push_back({x, y});
    }
    //X축 정렬하기
    sort(Vertex.begin(), Vertex.end());
}

//두 점 사이의 거리 제곱 반환
int dist(pii x, pii y)
{
    return (x.X-y.X) * (x.X-y.X) + (x.Y-y.Y) * (x.Y-y.Y);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    s.insert({Vertex[0].Y, Vertex[0].X});
    s.insert({Vertex[1].Y, Vertex[1].X});
    minDist = dist(Vertex[0], Vertex[1]);
    
    int idx = 0;
    for(int i=2; i<n; i++) {
        while(idx < i) {
            int xdist = Vertex[i].X - Vertex[idx].X;
            //만약 고려할 점과 탐색할 점 사이의 거리가 minDist보다 크다면
            //더 이상 고려할 필요가 없으므로 제거
            if(xdist*xdist < minDist)
                break;
            else {
                s.erase({Vertex[idx].Y, Vertex[idx].X});
                idx++;
            }
        }
        
        //범위 안에 들어가는 점들 모두 탐색
        auto st = s.lower_bound({Vertex[i].Y - sqrt(minDist), -INF});
        auto ed = s.upper_bound({Vertex[i].Y + sqrt(minDist), +INF});
        
        for(auto it = st; it != ed; it++)
            minDist = min(minDist, dist({it->Y, it->X}, Vertex[i]));
        s.insert({Vertex[i].Y, Vertex[i].X});
    }
    cout << minDist;
    
    return 0;
}

 

<set container>

https://blockdmask.tistory.com/79

[C++] set container 정리 및 사용법

 

<set lower_bound()>

https://salon.tistory.com/m/63

[C++] set lower_bound() 함수

 

<문제 반례 모음>

https://www.acmicpc.net/board/view/56990

글 읽기 - 반례 모아봤습니다.

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.