이동통신 기지국

휴대전화는 근처의 이동통신 기지국(cell tower)에 연결하여 통신한다. 어느 순간에 여러 기지국이 통신 범위 안에 있을 수 있지만, 휴대전화는 신호가 가장 강한 기지국 하나에만 연결한다. 이 문제의 목표는 휴대전화를 가진 여행자를 추적하는 것이다. 도로 위의 각 마일 표지(mile marker)에서 휴대전화가 어떤 기지국을 사용하는지 판단하고, 그 기지국이 바로 이전 표지에서와 달라지는 지점을 모두 보고한다.

각 기지국의 위치는 임의의 원점을 기준으로 한 정수 X-Y 좌표(단위: 마일)로 주어지며, 세기(power) 값을 가진다. 여행자는 여러 개의 직선 구간을 끝과 끝으로 이어 붙여 만든 도로를 따라 이동하며, 이 도로는 스스로 교차하지 않는다. 마일 표지는 도로를 따라 1마일마다 놓이고, 출발점이 0번 마일 표지이다.

도로가 마지막 마일 표지보다 0.5마일 이상 더 이어진 뒤 끝난다면, 그 끝점에는 다음 마일 번호를 붙인다. 예를 들어 길이가 8.6마일인 도로의 끝점은 9번 마일이 되고, 길이가 8.2마일인 도로는 8번 마일 표지에서 끝난다.

세기가 $p$인 기지국이 어떤 표지로부터 거리 $d$만큼 떨어져 있다면, 그 표지에서의 신호 세기는 $p / d^2$을 가장 가까운 정수로 반올림한 값이다(정확히 0.5인 경우는 올림한다). 기지국이 마일 표지와 정확히 같은 위치에 놓이는 경우는 없다. 각 표지에서 휴대전화는 신호 세기가 가장 큰 기지국을 사용하며, 둘 이상이 같은 세기로 최대라면 알파벳 순서가 가장 앞선 기지국을 사용한다.

풀이 예시(세 개의 예제 입력에 대응):

• 첫 번째 예제: 세기가 모두 1000인 기지국 A(1, 4)와 B(5, 4)가 있고, 도로의 구간은 격자를 따라간다. 표지 0과 1에서는 A가 더 강하다. 표지 2-4에서는 A와 B의 세기가 같으므로 알파벳이 앞선 A를 보고한다. 표지 5-9에서는 B가 더 강하다. 표지 10에서는 다시 세기가 같으므로 A를 보고하고, 이후 끝까지 A가 가장 강하다.
• 두 번째 예제: 기지국이 세 개다. A(0, 0)와 C(6, 6)은 세기 1000, B(6, 0)은 세기 600이다. 처음에는 A가 가장 강하고, 표지 3-8에서는 C가 가장 강하다. 도로는 (5, 2)에서 끝나는데, 이는 8번 마일에서 0.5마일을 넘게 더 간 지점이므로 끝점은 9번 마일이 된다. 이 끝점에서는 B가 가장 강해 8번 마일과 다르므로 끝점을 보고한다.
• 세 번째 예제: 두 번째와 비슷하지만 도로의 시작점이 다르고 기지국 B의 세기가 300이다. 처음에는 A가 가장 강하고, 표지 2-7에서는 C가 가장 강하다. (5, 2)에 있는 끝점은 7번 마일 표지에서 0.5마일이 채 안 되게 떨어져 있으므로, 그곳에서 B가 가장 강하더라도 표지로 붙이지 않는다.

입력은 하나 이상의 데이터 집합으로 이루어지며, 마지막에 0 하나만 있는 줄이 온다.

각 데이터 집합의 첫 줄에는 공백으로 구분된 두 정수 $T$와 $R$이 주어진다.

• $T$는 기지국의 수이며 $1 \le T \le 10$이다.
• $R$은 도로를 이루는 직선 구간의 수이며 $1 \le R \le 10$이다.

다음 $T$개의 줄에는 각각 한 기지국의 X좌표, Y좌표, 세기가 공백으로 구분되어 주어진다. 기지국에는 주어진 순서대로 'A', 'B', 'C', ... 라는 이름이 붙는다.

그다음 줄에는 도로를 정의하는 $R + 1$개 점의 좌표인 $2(R + 1)$개의 정수가 주어진다. 도로는 첫 번째 점에서 출발하여 나머지 점들을 순서대로 직선 구간으로 지난다.

모든 좌표는 0 이상 100 이하의 정수이고, 주어진 어떤 두 점도 같지 않다. 각 기지국의 세기는 1 이상 1,000,000 이하의 정수이다.

각 도로(데이터 집합)마다 한 줄을 출력한다. 그 줄은 공백 하나로 구분된 순서쌍들로 이루어진다. 각 순서쌍의 첫 번째 원소는 마일 표지 번호이고, 두 번째 원소는 그 표지에서 신호가 가장 강한 기지국의 이름(문자)이다. 0번 마일과, 가장 강한 기지국이 바로 이전 표지와 달라지는 모든 마일 표지에 대해 순서쌍을 출력한다. 각 순서쌍은 괄호로 감싸고 두 원소는 쉼표로 구분하며 괄호 안에는 공백을 넣지 않는다. 예: (5,B).