문제 링크
- https://icpc.me/25415
사용 알고리즘
- 불도저 트릭
시간복잡도
- $O(N^2 \log N)$
풀이
삼각형의 밑변을 구성하는 두 점을 구성합시다. 두 점을 연결하는 직선과의 거리가 $L$ 이상 $R$ 이하인 점의 개수를 구해야 합니다.
불도저 트릭을 하면서 파라메트릭 서치를 하면 $O(N^2 \log N)$에 해결할 수 있습니다.
또는 SIMD를 이용해 $O(N^3/24)$에 해결할 수도 있습니다.
삼각형의 밑변을 구성하는 두 점을 구성합시다. 두 점을 연결하는 직선과의 거리가 $L$ 이상 $R$ 이하인 점의 개수를 구해야 합니다.
불도저 트릭을 하면서 파라메트릭 서치를 하면 $O(N^2 \log N)$에 해결할 수 있습니다.
또는 SIMD를 이용해 $O(N^3/24)$에 해결할 수도 있습니다.