[BaekJoon] 백준 11663번 : 선분 위의 점

11663번 : 선분 위의 점

이분탐색을 통해 주어진 점이 선분 위에 있는지 확인하면 된다.

선분 위에 있는 점의 개수를 알아야하기 때문에 선분에서 가장 왼쪽에 있는 점, 가장 오른쪽에 있는 점의 index를 구해야한다.

가장 오른쪽에 있는 점의 index 에서 가장 왼쪽에 있는 점의 index 를 빼면 선분 위에 있는 점의 개수를 구할 수 있다.

가장 오른쪽에 있는 점이 선분 위에 있는 경우, 벗어난 경우와 가장 왼쪽에 있는 점이 선분 위에 있는 경우, 벗어난 경우를 구분해서 계산을 해주면 된다.

---

import sys


def calc_point(line_start, line_end):

    start = 0
    end = len(point) - 1
    while start <= end:
        left = (start + end) // 2
        if line_start <= point[left] <= line_end:
            end = left - 1
        else:
            if point[left] < line_start:
                start = left + 1
            elif point[left] > line_end:
                end = left - 1

    start = 0
    end = len(point) - 1
    while start <= end:
        right = (start + end) // 2
        if line_start <= point[right] <= line_end:
            start = right + 1
        else:
            if point[right] < line_start:
                start = right + 1
            elif point[right] > line_end:
                end = right - 1

    if point[left] >= line_start and point[right] <= line_end:
        return right - left + 1
    if point[left] < line_start and point[right] > line_end:
        return right - left - 1

    return right - left


def solution():
    for line in lines:
        print(calc_point(line[0], line[1]))


if __name__ == "__main__":
    N, M = map(int, input().split())
    point = list(map(int, input().split()))
    point.sort()
    lines = []
    for _ in range(M):
        line = tuple(map(int, sys.stdin.readline().rsplit()))
        lines.append(line)

    solution()