PS/BOJ
백준 BOJ 11683
JOFTWARE
2021. 6. 9. 12:16
문제
백준 BOJ
https://www.acmicpc.net/problem/11663
11663번: 선분 위의 점
첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과
www.acmicpc.net
사용 알고리즘
풀이
n^2이면 시간 초과가 나기 때문에 brute force는 안되고 이분 탐색을 써야 한다.
선분의 왼쪽 지점은 std:: lower_bound, 오른쪽은 std::upper_bound 사용하여 index를 각각 찾은 후 차이를 구해주면 된다.
점이 선분들 범위 밖을 아예 벗어났을 때 예외 처리를 따로 해주어야 함.
728x90