스위핑 알고리즘 2

[ BOJ ][JAVA][2261] 가장 가까운 두 점

www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 25345 4234 2120 15.700% 문제 2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값..

[ 개념 ] 47. 스위핑 알고리즘(Sweeping Algorithm)

> 스위핑 기법(Sweeping Algorithm) 이번에 소개해 드릴 기법은 스위핑 알고리즘(sweeping algorithm)이라고 하는데, 기법 개념 자체는 굉장히 간단하고 범용적인 대신에, 대부분 겁나게 어렵습니다. 기본적으로 다른 기법이나 자료구조와 반드시 얽힙니다. 스위핑이라는 건 그냥 어떤 선이나 공간을 한쪽에서부터 싹 쓸어버린다는 건데 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 뭔가를 해 주면 정답이 구해지는 형태입니다. - BOJ[2170] : 선 긋기 https://www.acmicpc.net/problem/2170 [ 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택..