본문 바로가기
Problem Solving/Online Judge

BOJ 13551 원과 쿼리

by hongjun7 2016. 11. 17.

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

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

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

 

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

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

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

'Problem Solving > Online Judge' 카테고리의 다른 글

BOJ 1995 폐쇄회로  (0) 2017.01.25
IOI 2005 Rivers  (0) 2017.01.02
Coder's high 2016 Round 1: Online F번  (0) 2016.06.08
BAPC 2005 Preliminaries D - Mandalas  (0) 2016.04.05
BOJ 11928 공기놀이  (0) 2016.02.10

댓글