https://www.acmicpc.net/problem/2261
2261번: 가장 가까운 두 점
첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있다.
www.acmicpc.net
문제해설
이 문제는 "라인스위핑"알고리즘으로 풀어 보았습니다.
이문제의 정답률은 15% 미만이고, 인터넷상에 해답이나 설명이 없었다면 10%도 안나올거라고 생각됩니다.
입력 조건에서, 좌표의 갯수가 10만개 까지 들어오기 때문에
당연히 O(n^2) 풀이로는 TLE이 나올 것입니다.
적어도 O(NlgN)정도의 풀이가 필요 합니다.
우선 이문제의 핵심은, 답을 만들 수 있는 최소한의 후보들로만 비교하는 것입니다.
편의를 위해, 초기에 기준을 잡고 기준을 기준으로
비교하면서 기준을 갱신해 나가며 답을 찾으면 됩니다.
( 주석으로 상세한 과정을 풀이했습니다 )
< 정렬 및 기준 잡기 >
// x축 정렬을 하는 이유 ? // x축 정렬을 통해 x의축의 차이만으로 최대값 후보에서 여러 점들을 제외 시킬 수 있다. sort(vec.begin(), vec.end()); // {y,x}으로 insert한 이유? // dx를 통해 if문으로 x축과의 거리는 처리 하였고, // map에 남아잇는 점들중에서 y축으로 lower_bound, upper_bound를 하기 위함이다. // = 0 인이 이유? // 어떤 값이든 크게 상관없지만 , INF보단 작고, -INF보단 커야한다.( lower_bound, upper_bound를 위해 ) m[{vec[0].second, vec[0].first}] = 0; m[{vec[1].second, vec[1].first}] = 0; ll ans = getDist(vec[0], vec[1]);
< 후보를 추가, 제외하면서 탐색 >
int pos = 0; for (int i = 2; i < n; i++) { // pos부터 i-1번까지 i번째점과 비교를 한다. while (pos < i) { // x축간의 거리 차이 int dx = vec[i].first - vec[pos].first; // pos( i 점 기준으로 현재 map 있는 가장 왼쪽 점 ) 과 i번째 점간의 x축 거리가 // 더 작다면 pos점은 여전히 후보에 포함될 수 있다. if (dx * dx <= ans) break; // pos(i 점 기준으로 현재 map 있는 가장 왼쪽 점) 과 i번째 점간의 x축 거리가 // 더 크다면 pos점은 더이상 더 작은 ans값을 만들어내지 못한다.( 후보에서 제외된다 ) m.erase({ vec[pos].second,vec[pos].first }); pos++; } // getDist 는 sqrt를 없이 반환했음으로... ll dis = sqrt(ans); // map에 남아있는 점들중에서 // 현재 ans보다 작아 질 수 있는 후보 점들을 확인 하기위해 left, right를 찾고 auto left = m.lower_bound({ vec[i].second - dis, -INF }); auto right = m.upper_bound({ vec[i].second + dis, INF }); // ans 갱신 for (auto l = left; l != right; l++) { ans = min(ans, getDist( {l->first.second,l->first.first}, vec[i])); } // i번째점은 당연히 뒤에 확인할게 있음으로 후보 점이 된다. m[{vec[i].second, vec[i].first}] = 0; }
그림으로 보나, 코드로 보나 쉽게 이해가 가지 않을 수 있을 것 같습니다.
때문에 중간 중간 주석으로, 과정에대해서 나름 상세하게 설명해 보았습니다.
전체코드
#include <iostream> #include <algorithm> #include <cmath> #include <map> #include <vector> #include <limits.h> using namespace std; #define INF INT_MAX typedef long long ll; // 문제에서 요구하는 거리는 거리의 제곱이기 때문에 sqrt를 사용하지 않았습니다. ll getDist(pair<int,int> a, pair<int,int> b) { int x1 = a.first; int y1 = a.second; int x2 = b.first; int y2 = b.second; return (x2-x1)*(ll)(x2 - x1) + (y2-y1)*(ll)(y2-y1); } vector<pair<int, int>> vec; map<pair<int, int>, int> m; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i < n; i++) { int x, y; cin >> x >> y; vec.push_back({ x,y }); } // x축 정렬을 하는 이유 ? // x축 정렬을 통해 x의축의 차이만으로 최대값 후보에서 여러 점들을 제외 시킬 수 있다. sort(vec.begin(), vec.end()); // {y,x}으로 insert한 이유? // dx를 통해 if문으로 x축과의 거리는 처리 하였고, // map에 남아잇는 점들중에서 y축으로 lower_bound, upper_bound를 하기 위함이다. // = 0 인이 이유? // 어떤 값이든 크게 상관없지만 , INF보단 작고, -INF보단 커야한다.( lower_bound, upper_bound를 위해 ) m[{vec[0].second, vec[0].first}] = 0; m[{vec[1].second, vec[1].first}] = 0; ll ans = getDist(vec[0], vec[1]); // pos = 0 부터, i = 2 부터인 이유? // 편의상 첫번째점과 두번째점을 (x축 정렬 기준 ) 을 기준으로 잡았다. // 밑의 코드의 for문을 돌리는대신 기준을 잡았다고 보면 된다. /* for(int i = 0 ; i < 2; i ++){ ... } */ int pos = 0; for (int i = 2; i < n; i++) { // pos부터 i-1번까지 i번째점과 비교를 한다. while (pos < i) { // x축간의 거리 차이 int dx = vec[i].first - vec[pos].first; // pos( i 점 기준으로 현재 map 있는 가장 왼쪽 점 ) 과 i번째 점간의 x축 거리가 // 더 작다면 pos점은 여전히 후보에 포함될 수 있다. if (dx * dx <= ans) break; // pos(i 점 기준으로 현재 map 있는 가장 왼쪽 점) 과 i번째 점간의 x축 거리가 // 더 크다면 pos점은 더이상 더 작은 ans값을 만들어내지 못한다.( 후보에서 제외된다 ) m.erase({ vec[pos].second,vec[pos].first }); pos++; } // getDist 는 sqrt를 없이 반환했음으로... ll dis = sqrt(ans); // map에 남아있는 점들중에서 // 현재 ans보다 작아 질 수 있는 후보 점들을 확인 하기위해 left, right를 찾고 auto left = m.lower_bound({ vec[i].second - dis, -INF }); auto right = m.upper_bound({ vec[i].second + dis, INF }); // ans 갱신 for (auto l = left; l != right; l++) { ans = min(ans, getDist( {l->first.second,l->first.first}, vec[i])); } // i번째점은 당연히 뒤에 확인할게 있음으로 후보 점이 된다. m[{vec[i].second, vec[i].first}] = 0; } cout << ans << "\n"; return 0; }
'알고리즘 > [C++]BOJ' 카테고리의 다른 글
| [백준BOJ] 1298 노트북의 주인을 찾아서 (0) | 2019.10.14 |
|---|---|
| [백준BOJ] 11377 열혈강호 3 (0) | 2019.10.14 |
| [백준BOJ] 1671 상어의 저녁식사 (0) | 2019.10.14 |