jeoffrey0522   1년 전

제곱근 분할법(채점 번호: 85023068, 86980972)를 저격한 데이터입니다.

data.zip

점들의 분포에 따라, 제곱근 분할법, 쿼드트리나 kd-tree 등 orthogonal partitioning를 이용한 풀이의 시간복잡도는 최악 O(NQ)이며, 상수로 인해 brute-force보다 느리게 돌아갈 수 있습니다. 예시는 다음과 같습니다.

1. 점들이 고정된 원 위에 분포.

2. 점과 쿼리들이 특정 버켓 내부에 균일하게 분포.

- 단순히 입력 좌표의 범위만 좁히면 됩니다. 특히, 버켓의 범위를 상수로 설정한 풀이는 모두 시간 초과를 받아야 합니다.

3. 점들이 특정 k개의 버켓 중 하나에 속해 있고, 임의의 쿼리가 모든 k개의 버켓들과 교차.

- 가장 일반적인 경우입니다. 예시로, 고정된 두 점을 지나는 원들의 집합을 상상할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.