Mission Possible

정부 비밀 요원 Allen은 마피아의 작전에 관한 중요한 정보를 알아내기 위해 마피아의 비밀 기지에 잠입하는 임무를 맡았다.

비밀 기지는 직교 좌표계에서 $(x_L, y_L)$, $(x_L, y_R)$, $(x_R, y_L)$, $(x_R, y_R)$로 둘러싸인 직사각형이며, 여기서 $x_L < x_R$이고 $y_L < y_R$이다. 비밀 기지 안에는 $N$개의 센서가 설치되어 있다. $i$번째 센서는 $(x_i, y_i)$에 위치하고 유효 감지 반경 $r_i$를 가지며, $(x_i, y_i)$로부터 거리가 $r_i$보다 엄격히 작은 사람을 감지할 수 있다. 즉, $i$번째 센서는 $(x_i, y_i)$와 $(x_a, y_a)$ 사이의 유클리드 거리가 $r_i$보다 엄격히 작은 경우에만 위치 $(x_a, y_a)$에 있는 사람을 감지한다. 또한 임의의 두 센서 $i$와 $j$ 사이의 유클리드 거리는 $r_i + r_j$보다 엄격히 크다는 것이 알려져 있다. 두 점 $(x_a, y_a)$와 $(x_b, y_b)$ 사이의 유클리드 거리는 $\sqrt{|x_a - x_b|^2 + |y_a - y_b|^2}$이다.

Allen은 위치 $(x_s, y_s)$에서 잠입 임무를 시작하고, 목표는 $(x_t, y_t)$에 있다. Allen은 직선으로 매우 빠르게 달릴 수 있지만, 달리는 궤적을 바꾸려면 발을 디뎌야 하므로 추가 시간이 필요하다. 빠른 주자이지만 달리는 동안 어떤 센서에도 감지되지 않아야 한다. 즉, 달리는 궤적 위의 어떤 점도 센서의 유효 감지 반경 안에 엄격히 들어가서는 안 된다.

$P = \{(x_{p1}, y_{p1}), \ldots, (x_{p|P|}, y_{p|P|})\}$를 Allen이 달리는 궤적을 바꾸는 위치의 집합이라고 하자. 그러면 $P$를 사용한 Allen의 달리는 궤적은 $(x_s, y_s) \to (x_{p1}, y_{p1}) \to \cdots \to (x_{p|P|}, y_{p|P|}) \to (x_t, y_t)$이며, 여기서 $(x_a, y_a) \to (x_b, y_b)$는 Allen이 $(x_a, y_a)$에서 $(x_b, y_b)$까지 직선으로 달린다는 것을 의미한다. 집합 $P$는 $P$를 사용했을 때 Allen이 어떤 센서에도 감지되지 않고 비밀 기지 밖으로 나가지 않으면 실행 가능하다. 단, Allen은 비밀 기지 둘레를 따라 달릴 수 있다. $P$의 원소 $(x_p, y_p)$의 $x_p$와 $y_p$는 정수일 필요가 없으며 실수일 수 있다.

이 문제에서 여러분의 임무는 1000개 이하의 점을 포함하는 실행 가능한 $P$를 하나 찾는 것이다.

입력은 다섯 정수 $N$ $x_L$ $y_L$ $x_R$ $y_R$을 포함하는 한 줄로 시작한다 ($0 \le N \le 50$; $0 \le x_L < x_R \le 1000$; $0 \le y_L < y_R \le 1000$). 이는 각각 센서의 개수와 비밀 기지 $(x_L, y_L, x_R, y_R)$를 나타낸다. 다음 줄에는 두 정수 $x_s$ $y_s$가 주어진다 ($x_L < x_s < x_R$; $y_L < y_s < y_R$). 이는 Allen의 시작 위치를 나타낸다. 다음 줄에는 두 정수 $x_t$ $y_t$가 주어진다 ($x_L < x_t < x_R$; $y_L < y_t < y_R$). 이는 Allen의 목표 위치를 나타낸다. $x_s \ne x_t$ 또는 $y_s \ne y_t$임이 보장된다. 다음 $N$개의 줄 각각에는 세 정수 $x_i$ $y_i$ $r_i$가 주어진다 ($x_L < x_i - r_i < x_i + r_i < x_R$; $y_L < y_i - r_i < y_i + r_i < y_R$; $1 \le r_i \le 1000$). 이는 $(x_i, y_i)$에 위치한 유효 감지 반경 $r_i$의 센서를 나타낸다. 임의의 두 센서 $i$와 $j$ 사이의 유클리드 거리는 $r_i + r_j$보다 크다는 것이 보장된다. 또한 $(x_s, y_s)$와 $(x_t, y_t)$에서 임의의 센서 $i$까지의 유클리드 거리는 $r_i$보다 크다는 것이 보장된다.

실행 가능한 $P$의 크기를 나타내는 정수를 한 줄에 출력한다. 다음 $|P|$개의 줄 각각에는 두 실수를 공백 하나로 구분하여 출력한다. $j$번째 줄에는 $P$의 $j$번째 점 $(x_j, y_j)$를 나타내는 $x_j$ $y_j$를 출력한다. 1000개 이하의 점을 포함하는 실행 가능한 $P$를 아무거나 출력해도 된다.

출력이 부동 소수점이므로 $\epsilon = 10^{-6}$을 사용하여 출력을 검증한다. $Q_1 = (x_s, y_s)$, 모든 $1 \le j \le |P|$에 대해 $Q_{j+1} = P_j$, $Q_{|P|+2} = (x_t, y_t)$라고 하자. 그러면 $P$는 1000개 이하의 점을 포함하고 다음 조건을 모두 만족할 때에만 올바른 것으로 간주된다.

• 모든 $1 \le k \le |P|$에 대해 $x_L - \epsilon \le x_{pk} \le x_R + \epsilon$이고 $y_L - \epsilon \le y_{pk} \le y_R + \epsilon$이다 (Allen이 비밀 기지 밖으로 나가지 않는다).
• 모든 $1 \le k < |Q|$에 대해 $S_k$를 $Q_k$와 $Q_{k+1}$을 연결하는 선분이라고 하자 (Allen이 직선으로 달린다). 모든 $1 \le i \le N$에 대해 $(x_{k,i}, y_{k,i})$를 $S_k$ 위에서 $i$번째 센서의 위치 $(x_i, y_i)$에 가장 가까운 점이라고 하자. $d_{k,i}$를 $(x_{k,i}, y_{k,i})$와 $(x_i, y_i)$ 사이의 유클리드 거리라고 하자. 그러면 $r_i \le d_{k,i} + \epsilon$을 만족해야 한다 (Allen이 어떤 센서에도 감지되지 않는다).
• $Q$의 모든 점은 서로 다르다. 두 점 $(x_a, y_a)$와 $(x_b, y_b)$는 $|x_a - x_b| > \epsilon$ 또는 $|y_a - y_b| > \epsilon$일 때에만 서로 다른 것으로 간주된다.