[C++] 가장 가까운 두 점

백준 2261번이다

직무 교육 들으면서 추가로 풀어보았던 문제

solved ac 플레 3이라는 꽤나 높은 난이도의 문제였다

 

 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <math.h>
 
#define ll long long
 
using namespace std;
 
typedef struct pair<int,int> pii; 
pii points[100001];
 
ll distance(int i,int j,int x, int y){
    return (i-x)*(i-x) + (j-y)*(j-y);
}
 
int CPair(int start, int end){
    if(end-start<=2){
        ll res = distance(points[start].first, points[start].second,points[start+1].first, points[start+1].second);
        if(end-start==2) res = min(res,distance(points[start+1].first, points[start+1].second,points[end].first,points[end].second));
        return res;
    }
 
    int mid = (start+end)/2;
    int median = points[mid].first;;
 
    ll delta_S1 = CPair(start,mid);
    ll delta_S2 = CPair(mid+1,end);
 
    ll delta_d = min(delta_S1,delta_S2);
 
    vector<pii> vec;
 
    for(int i = start ; i <= end ; i++){
        if(delta_d > (points[i].first-median)*(points[i].first-median)){
            vec.emplace_back(make_pair(points[i].second,points[i].first));
        }
    }
 
    sort(vec.begin(),vec.end());
 
    for(int i = 0 ; i < vec.size() ; i++){
        for(int j = i+1 ; j < vec.size() ; j++){
            int y_distacne = vec[j].first - vec[i].first;
            if(y_distacne*y_distacne >= delta_d) break;
            delta_d = min(delta_d,distance(vec[i].first,vec[i].second,vec[j].first,vec[j].second));
        }
    }
    return delta_d;
}
 
int main(){
 
    int N;
    scanf("%d",&N);
    vector<int> y;
    for(int i = 0 ; i < N ; i++){
        scanf("%d %d",&points[i].first,&points[i].second);
    }
 
    sort(points,points+N);
 
    bool hasEqual = false;
    for(int i = 1 ; i < N ; i++){
        if(points[i].first == points[i-1].first && points[i].second == points[i-1].second)
            hasEqual = true;
    }
    if(!hasEqual) printf("%d\n",CPair(0,N-1));
    else printf("%d\n",0);
    
}

 

 

아이디어가 정말 중요한 문제 같다

문제 설명은 한 줄로 끝나는 정말 간단한 문제지만 100000 * 100000을 단순하게 한다면 당연히 시간 초과가 날 것 이다

이를 해결하기 위해 분할 정복을 이용한다

 

먼저 모든 좌표를 정렬한다 ( line 62 )

그 다음 혹시 같은 위치에 점이 두 개 있을 수도 있으니 같은 점이 있는지 체크 한 후 같은 위치에 있다면 거리가 0이니까 바로 0을 출력해주었다 ( line 70 )

 

같은 위치에 점이 없다면 이제 분할 정복을 해야 한다

분할 정복이 시간복잡도를 만족한다는 것은 수업시간에 배워서 이해는 했지만 블로그에 다시 정리하기는 너무 방대하다,,

그냥 코드만 정리해야겠다ㅎㅎ

 

먼저 전체 점들을 왼쪽,오른쪽 반으로 나눈다 ( line 25 ~ 29 )

이 때 나뉜 점들이 3개 이하가 되면 점 3개 사이의 거리를 구하는 것이 어렵지 않으므로 3개 중 가까운 두개의 거리를 return 한다 ( line 19 ~ 23 )

 

이 때 거리를 구할때는 sqrt는 오래 걸리기 때문에 그냥 제곱 상태를 그대로 유지했다

 

이제 왼쪽과 오른쪽들 점들 각각에서 가장 가까운 거리를 알 수 있다 ( line 31 )

하지만 문제는 지금까지는 왼쪽과 오른쪽 각각에서 가장 가까운 거리는 알 수 있으나 만약 가장 가까운 두 점이 한개는 왼쪽, 나머지 한개는 오른쪽에 있는 경우이다

 

그런 케이스를 찾기 위해 좌표를 넣을 벡터를 하나 선언해주었다 ( line 33 ) 

이 벡터에는 왼쪽 오른쪽을 나누는 중점의 x값과의 차이가 왼쪽과 오른쪽 각각에서 가장 가까운 거리보다 작은 점들을 넣어준다 ( line 35 ~ 39 )

그림으로 보자면 이런 느낌

 

점들을 sorting 되어 있으므로 파란색 - 0, 주황색 - 1, 검은색 - 2, 노란색 - 3, 연두색 - 4 와 같은 index를 가질 것 이다

이 때 0,1,2는 왼쪽으로 4,5는 오른쪽으로 나뉘어 2개 3개의 적은 수에서 가까운 거리를 가져온다

 

만약 왼쪽 점들 사이의 가장 가까운 거리가 5, 오른쪽 저들 사이의 가장 가까운 거리가 7이라고 하자

또한 검은색 점인 중점의 x좌표가 10이라고 하자

파란색 점, 연두색 점의 x 좌표와 검은색 점의 x좌표는 5를 넘는 큰 값이기 때문에 벡터에 넣어주지 않는다

주황색과 노랑색 점의 x좌표는 검은색의 x좌표와 가깝기 때문에 벡터에 넣어준다

이 때 단순히 x 좌표 차의 절대값으로 계산하는 것이 아니라 제곱을 해준다

왜냐하면 유클리디안 거리를 애초에 제곱식으로 사용하고 있기 때문이다

 

이제 벡터에는 나뉘어있었지만 사실 가장 가까운 점일 수 있었던 점들이 모여있다

이제 이 점들을 y좌표로 sorting 해주어야 한다

나는 y좌표로 sorting을 따로 짜기 귀찮아서 애초에 벡터에 넣을 때 y,x로 넣어서 sorting 했다 ( line 35 ~ 41 )

 

밑에서부터 보면서 index i를 기준으로 점점 올라간다

이 때 이 점들의 y좌표의 차가 또 5를 넘는다면 비교할 의미가 없기 때문에 break로 종료해준다 ( line 46 )

아래서부터 위로 올라가며 점들의 거리를 비교하고 만약 더 가까운 점의 쌍을 찾는다면 min 값을 update 해준다 ( line 47 )

 

내가 만든 사진에서는 노랑색이 주황색과 가장 가까운 예시를 생각하면서 만들어보았다

vec에는 검은색 - 0, 노란색 - 1, 주황색 - 2 상태로 sorting 되어 있고 검은색은 그 다음 좌표인 노란색과 5이상의 차이가 나기 때문에 break로 바로 종료

노란색은 주황색과 비교하여 update를 해준다

이 때 break를 쓰지 않는다면 시간복잡도가 너무 증가하기 때문에 꼭 넣어주어야한다

만약 break를 쓰지 않을거라면 sorting을 한 의미조차 없어진다

 

코드는 지금 보니 그렇게 길지 않지만 기하 파트가 약해서 공부할때와 코드 짤 때 너무 힘들었다ㅠㅠ

이제 알고리즘 대회도 잘 안나가니 기하 파트를 어디서 써먹을지는 모르겠지만 몇 문제 더 풀어봐야겠다