백준 5620번 가장 가까운 두 점의 거리

문제

평면상에 n개의 점 (P1, .... ,  Pn) 이 놓여져있다고 했을 때, 거리가 최소인 두 개의 점을 구하고 그 거리를 알고 싶다.

문제풀이

사용한 알고리즘 :  sweep line

(0) 들어가기 전에

 이 문제는 백준 2261번 문제와 거의 같습니다.
 백준님의 글 ( https://www.acmicpc.net/blog/view/25 ) 을 읽고 코드를 작성하였습니다.

(1) 코드 6~17

 각 정점을 받을 struct 를 짜주었습니다. set에 넣기 위해 operator을 함께 짜줍니다.

(2) 코드 33~34, 18~20

 각 정점을 x 좌표가 작은 것부터 오름차순으로 정렬합니다.

(3) 코드 35

 각 정점을 정렬된 차례로 탐색하며, 매 탐색시 구하고자 하는 답(이하 ans)을 최신화 합니다.
 i번째 정점 탐색을 진행할 때, 이전에 최신화한 ans보다 i번째 정점에서 멀리 떨어진 정점은 볼 필요가 없습니다.
따라서 i번째 정점 기준으로 x좌표 기준 ans 거리만큼, y좌표 기준 위,아래 각각 ans거리만큼 사각형을 만들어 이 안의 정점들만을 탐색할 것입니다. 
 이를 위해 가능성 있는 정점을 set으로 저장합니다.
 ( set 안에 저장된 정점들은 y좌표 기준으로 정렬됩니다. )
 중복을 피하기 위해 i번째 정점을 탐색시 i번째 정점 이전의 정점들과의 거리만 볼 것입니다.
(1번째와 5번째 정점 사이의 거리와 5번째와 1번째 정점 사이의 거리는 같습니다.)

(4) 코드 35~67

 우선 정렬된 정점들 중 처음 2개를 ans로 놓고, 과정(3) 에 만든 set에 그 두 정점을 넣습니다. (탐색이 끝난 정점은 set에 넣어줍니다.)
 이후 3번째 정점부터 탐색을 시작합니다.
 과정 (3)에서 말했듯이 i번째 정점을 탐색할 시 정점들을 추려서 탐색할 것입니다. 
 이를 위해
 1. i번째 정점 기준 x축으로 ans 거리 보다 멀리 있는 것은 set에서 지웁니다. ( 정점은 x좌표 기준으로 정렬되어 있기 때문에 i번째 정점 이후 정점들도 지워진 정점을 볼 필요 없습니다. )
 2. i번째 정점 기준 y축으로 위,아래로 ans 거리 안쪽에 있는 정점들만 탐색합니다.
 ( 이를 위해 정점 struct의 operator로 set을 y좌표 기준으로 만들어 준 것입니다. )
 이때 lowerbound, upperbound 를 사용해줍니다.