BOJ 13551 원과 쿼리

문제 링크 : https://www.acmicpc.net/problem/13551

풀이 : 점들이 분포하는 영역을 정사각형 블록들로 나누어 생각해 볼 수 있다.

 질문으로 어떤 원이 주어졌을 때에 정사각형 블록과 원의 공통된 부분이 있다면, 해당 블록에 속한 점들이 일일이 원에 속하는 지 확인하는 방법을 시도해 볼 수 있다. 원과 정사각형 블록과의 관계는 다음과 같이 크게 3가지로 나뉜다.

 

1. 원 내부에 정사각형 전부가 들어가는 경우
 : 정사각형의 꼭짓점들이 모두 원에 속하는 것과 동치

2. 원 외부에 정사각형 전부가 위치한 경우
: 원의 중심이 정사각형 외부에 있고, 정사각형의 각 변과 원의 중심과의 최소 거리가 반지름보다 모두 큰 것과 동치

3. 이 외의 경우
: 해당 블록에 속한 점들과 원의 관계를 살펴보면 된다.