[백준 / BOJ] 14746 Closest Pair

문제

출처 : www.acmicpc.net/problem/14746

14746번: Closest Pair

수평선 c1위에있는 점 P들이 있고

(c1, P1) (c1, P2) (c1, P3)...

수평선 c2위에있는 점 Q들이 있다.

(c2, Q1) (c2, Q2) (c2, Q3)..

(단, 모든 점 P들은 전부 다르며 Q또한 마찬가지다.)

이때, 점 P와 Q의 거리가 최솟값을 갖는 쌍의 갯수와 그때의 최솟값을 출력하라는 문제이다.

 

 

풀이

c1과 c2는 고정되어있기 때문에 각 점들의 X좌표만 비교해주면 되는 문제였다.

(한 벡터에 전부 넣고 정렬하면 가장 가까운 점들끼리 모이게됨) 이 아이디어를 이용해 문제를 풀었다.

 

1. 2차원 벡터를 선언한다. 벡터에는 {점의 X좌표, 점이 P점인지 Q점인지 나타내줌} 이런식으로 원소를 집어넣어줬다.

2. 점들을 입력받고 벡터를 정렬해준다. (한 벡터에 전부 넣고 정렬하면 가장 가까운 점들끼리 모이게됨)

3. vec[i].second != vec[i+1].second 일때가 그 점이 가질수있는 최솟값 이므로 최솟값을 계산하고 저장되어있는 최솟값과 비교해준다.

 

위를 반복하면 끝.

 

P의 정점의 갯수가 50만, Q가 50만이라서 정렬없이 완전탐색을 하면 시간초과가 난다.

처음에는

1. P가 음수일때,

-> Q가 음수라면, 절댓값 작아짐

-> Q가 양수라면, 절댓값 커짐

 

2. P가 양수일때,

-> Q가 음수라면, 절댓값 커짐

-> Q가 양수라면, 절댓값 작아짐

이런 느낌으로 음수와 양수를 나눠서 이분탐색으로 풀려고했다........

 

또 (한 벡터에 전부 넣고 정렬하면 가장 가까운 점들끼리 모이게됨) 이 아이디어를 생각했어도 구현이 문제였는데,

문제 조건을 잘 안읽고 P와 Q에 같은 정점이 존재할수도 있다고 생각했다.

만약, 같은 조건이 존재하면

P가 -1이 1000개

Q가 1이 1000개 일때, 

출력은 (2 + |c1 - c2| , 1000) 이 되어야하는데 위의 알고리즘 처럼하면  (2 + |c1 - c2| , 1)이 출력된다.

(붙어있는 쌍이 P의 마지막 -1과 Q의 첫번째 1 밖에 없기때문..)

조건을 잘 읽고 풀어야하는 문제였다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14746%20Closest%20Pair/main.cpp

devxb/JJUNalgo