Informática - Nível Avançado - Semana 1

A Erupção Do Vulcão

"O vulcão entrou em erupção!" Gritou Arnaldo, tentando acordar Bernardo.

"Você tem que salvar Carlos, ele está preso no laboratório ao lado do vulcão!" disse Arnaldo.

Você pode imaginar a estrada entre a base e o laboratório como um retângulo com ponto inferior esquerdo em $(0,0)$ e canto superior direito em $(W,L)$ . Existem $n$ buracos cheios de lava que veio do vulcão. O $i$ -ésimo buraco é um círculo com centro no ponto $(x_i,y_i)$ , com raio $r_i$ . Os buracos podem se interceptar para formar buracos maiores.

Bernardo inicia sua missão em qualquer ponto no lado inferior do retângulo (qualquer ponto $(0...W,0)$ ), e tem que chegar à qualquer ponto no lado superior do retângulo (qualquer ponto $(0...W,L)$ para salvar Carlos.

Nenhum buraco intersecta com o lado inferior ou superior do retângulo.

Bernardo pode levar roupas especiais, resistentes à lava, em sua mochila, também resistente à lava. Cada roupa especial o permite nadar em um ou mais buracos que se intersectam. Uma vez que Bernardo usa uma roupa, e sai do buraco, ele tem que jogar essa roupa fora. Bernardo tem que permanecer dentro da rua constantemente. Note que se dois buracos são tangentes, Bernardo não pode atravessá-los sem usar uma roupa especial.

Qual o menor número de roupas especiais que Bernardo tem que levar em sua missão, para salvar Carlos?

Entrada:

A primeira linha de entrada contém um inteiro $T$ , o número de casos-teste. A primeira linha de cada caso-teste contém 3 inteiros: $n$ , $W$ e $L$ , o número de buracos, a largura e a altura do retângulo, respectivamente. Cada uma das próximas $n$ linhas contém 3 inteiros: $x_i$ , $y_i$ e $r_i$ , as coordenadas do centro e o raio do $i$ -ésimo buraco.