JOI 2012/2013 Spring Training Camp Day1 4번 - JOI Poster 풀이

[JOI 2012/2013 Spring Training Camp Day1 4번 - JOI Poster]

https://www.acmicpc.net/problem/17745

17745번: JOI Poster

가로가 $W$, 세로가 $H$인 직사각형 평면 위에 $N$개의 점이 주어집니다. 이때 서로 다른 점 4개를 골라 $A$, $B$, $C$, $D$라고 해봅시다. 점 $A$를 중심으로 하고 점 $B$를 지나는 원을 $O_1$, 점 $C$를 중심으로 하고 점 $D$를 지나는 원을 $O_2$라 합시다. 이때 다음 두 조건을 모두 만족하는 $A$, $B$, $C$, $D$ 조합의 개수는 총 몇 개일까요?

1. $O_1$과 $O_2$는 평면을 벗어나선 안 됩니다.
2. $O_2$는 $O_1$ 내부에 있어야 합니다. $O_1$과 $O_2$가 서로 접하지 않아야 합니다.

 
 
두 점 $A$, $B$를 잇는 선분은 원 $O_1$의 반지름이므로, $O_1$과 $O_2$는 항상 하나의 원으로 결정됨을 알 수 있습니다. (원이 하나로 결정되기 위해서는 원의 중심과 원의 반지름이 필요합니다. [참고]) 
조건 1부터 살펴봅시다. 조건 1을 만족하기 위해서는 원의 중심 좌표를 $(x, y)$라 하고, 반지름의 길이를 $r$이라 할 때,

1. $x-r$이 음수
2. $y-r$이 음수
3. $x+r$이 $W$를 초과
4. $y+r$이 $H$를 초과

이상의 4가지 중 하나라도 만족해선 안 됩니다.
 
다음으로 조건 2를 살펴봅시다. $O_2$가 $O_1$ 안에 있기 위해서는 $O_1$의 반지름이, $O_2$의 반지름과, $O_1$의 중심과 $O_2$의 중심 사이의 거리의 합보다 커야 합니다. [참고2] 즉 $O_1$의 반지름을 $r_1$, $O_2$의 반지름을 $r_2$, $O_1$의 중심과 $O_2$의 중심 사이의 거리를 $d$라 할 때, $r_1 > r_2 + d$를 만족해야 합니다.
 
여기서 끝난다면 이 문제와 별반 다르지 않은 문제가 되겠지만, 이 문제는 계산과정에서 실수 오차를 고려해야합니다. 실수 오차를 피하는 가장 좋은 방법은 실수 계산을 하지 않는 것입니다. 어떻게 할 수 있을까요?
 
$\sqrt{a} > \sqrt{b} + \sqrt{c}$를 만족하는지 살펴봐야 합니다. 양변을 제곱해봅시다.

$a > b+c + 2\sqrt{bc}$

이고, 식을 정리하면

$a-b-c > 2\sqrt{bc}$

이때 우변은 항상 $0$ 이상이므로 좌변도 이를 만족해야 합니다. 
 
      (i) $a-b-c \geq 0$
 
양변이 0 이상이므로 양변을 제곱하여도 부등호 방향은 바뀌지 않습니다. 제곱하면,
 
      (ii) $(a-b-c)^2 > 4bc$
 
 
$N$이 $50$으로 매우 작으므로, 가능한 $A$, $B$, $C$, $D$의 경우를 모두 탐색하며 이상의 조건들을 만족할 때마다 카운트를 해줍시다. 최종 시간복잡도는 $O(N^4)$입니다.