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 |