SPOJ Brasil

A final mundial do ICPC será realizada em um luxuoso hotel com um grande salão de baile. Uma refeição será servida nesse salão e os organizadores decidiram decorar suas paredes com fotos de times campeões de anos anteriores.

Para evitar críticas sobre o favorecimento de alguns times sobre outros, o comitê organizador quer ter certeza que todas a fotos estão propriamente iluminadas. A única maneira direta que eles acharam para fazer isso é garantindo que cada foto tenha pelo menos uma lâmpada que a ilumine diretamente.

Dessa maneira, o perímetro da parede do salão pode ser dividida em partes iluminadas (onde as fotos podem ser colocadas) e partes escuras (que não servem para colocar fotos).

O salão tem a forma de uma caixa e contém várias lâmpadas. Cada lâmpada emite luz em todas direções, mas essa luz pode ser bloquada por colunas. Todas as colunas do salão tem forma cilíndrica e vão do chão ao teto, assim a luz não consegue passar através ou sobre elas. As colunas são obviamente colocadas de forma que a parte circular esteja paralela ao chão do salão.

Qualquer ponto p no perímetro da parede é dito iluminado se existe uma linha (um raio de luz) que começa na lâmpada, acaba em p e não toca ou passa através de nenhuma coluna.

Visão aérea de três salões com suas lâmpadas, colunas e áreas iluminadas e escuras.

Sua tarefa como ajudante da organização do ICPC é examinar a planta do salão e determinar a extensão total de seções iluminadas da parede. A planta consiste de um retângulo indicando uma visão aérea do salão, com as lâmpadas e colunas marcadas nela.

Entrada

Cada caso de teste consistirá de várias linhas. A primeira linha terá quatro inteiros: L, o número de lâmpadas, C, o número de colunas, X, o tamanho do salão na coordenada x e Y, o tamanho do salão na coordenada y. O canto inferior esquerdo está em (0, 0) enquanto o canto superior esquerdo está em (X, Y).

As próximas L linhas terão dois inteiros, cada um representando as coordenadas x e y de cada lâmpada. As últimas C linhas do caso de teste terão três inteiros cada, representando as coordenadas x e y do centro de uma coluna e seu raio, nessa ordem. Você pode assumir que 1 <= L, C <= 103 e 4 <= X, Y <= 106. Também, para todos os pares de coordenadas (x, y), 0 < x < X e 0 < y < Y, tanto para lâmpadas quanto para as posições centrais da coluna. Todos os raios das colunas serão positivos. Finalmente, nenhuma coluna irá se sobrepor, apesar de elas poderem se tocar, e nenhuma coluna irá encostar ou se intersectar com a borda do salão. Nenhuma lâmpada ficará dentro de uma coluna ou em seus domínios e nenhuma lâmapada ficará no mesmo lugar que outra. A entrada acaba com L = C = X = Y = 0.

Saída

Para cada caso de teste, imprima uma única linha com o comprimento total das partes iluminadas da parede periférica do salão. O resultado deve ser imprimido como um número real com exatamente quatro casas decimais, com a última casa decimal arredondada para cima.

Exemplo

Entrada
2 1 8 8
6 6
2 6
4 4 2
1 4 7 7
3 3
2 4 1
4 2 1
2 2 1
4 4 1
2 2 9 7
1 2
5 5
3 3 2
7 5 1
0 0 0 0

Saída
28.0000
0.0000
25.8214