문제
백준 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
'PS > BOJ' 카테고리의 다른 글
| 백준 BOJ 2616 소형기관차 (0) | 2021.06.11 |
|---|---|
| 백준 BOJ 10800 컬러볼 (0) | 2021.06.11 |
| 백준 BOJ 5582 공통 부분 문자열 (0) | 2021.06.08 |
| 백준 BOJ 20003 거스름돈이 싫어요 (0) | 2021.06.07 |
| 백준 BOJ 1027 고층 건물 (0) | 2021.06.07 |