스위핑2 [백준] 2261번: 가장 가까운 두 점 | C++ 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 브루트포스로 O(N^2) 시간에 해결할 수 있지만, O(NlogN)으로 푸는 방법을 알아보고자 한다. 정답코드 1. x좌표 기준으로 오름차순 정렬한다. 2. 0번째와 1번째 거리를 최소 거리(min_d)라고 가정한다. 3. 현재 살펴보는 좌표가 i번째 (x, y)라고 하면 [x - min_d, x] 범위에 해당하는 좌표를 "더 가까울 수 있는" 좌표 후보에 추가한다. 4. [y - min_d, y + min_d] 에 해당하는 좌표.. 2023. 6. 5. [기하] C++의 복소수 클래스 complex 기하 문제를 풀 때 c++의 복소수 클래스 complex를 사용할 수 있다. 이 클래스를 이용하면 점과 벡터를 복소수 형태로 표현할 수 있고, 클래스의 기능을 이용하여 점과 벡터를 다룰 수도 있다. typedef long long C; // 정수 좌표를 써도 되는 경우 // typedef long double C; // 정수 좌표를 쓸 수 없는 경우 typedef complex P; #define X real() #define Y imag() 정수 계산이 정확하기 때문에 정수좌표를 사용하는 것을 권장한다. 함수 complex 클래스에는 기하 문제를 풀 때 활용할 수 있는 함수를 제공한다. long double 자료형임을 주의하자. abs(v) 벡터 v={x, y}의 길이를 계산하는 함수이다. sqrt(x.. 2023. 6. 1. 이전 1 다음
