La gran bomba de explosión extraña de destrucción masiva Z

Autor: Gabriel Rea Subido por: Javier Ojeda Jorge

La plaga zombie ha ido ganando a la humanidad en la gran guerra Z. Ahora que la humanidad ha despertado de su estupor inicial frente al inicio del apocalipsis Zombie, llegó la hora del contraataque! Tu equipo está evaluando diferentes armas de destrucción masiva, en este caso, bombas creadas por cient´ıficos de poca cordura. Estas bombas crean explosiones rectangulares!, muy efectivas en entornos urbanos.

Los científicos han ofrecido a tu equipo una cantidad N de bombas rectangulares antizombie de diferentes tipos. En este momento se encuentran en la etapa de preparaciín de los lugares en los que las bombas llegarían a formar una explosión más efectiva que nos libre de la infestación zombie.

Dada una posible locación de las explosiones, determinar cual es el área total cubierta por las explosiones. En la figura se puede ver que el área de las 4 explosiones es de 30 (unidades cuadradas).

Entrada

La entrada comienza con un número NC, el número de casos de prueba. Por cada caso de prueba:

El número N (1 ≤ N ≤ 100) de bombas rectangulares. A continuación, siguen N líneas, cada
una con la descripción de un rectángulo. La descripción consiste en 4 números enteros ax, ay, bx, by que representan 2 puntos a, b: las esquinas inferior izquierda y superior derecha respectivamente, 0 ≤ ax < bx ≤ 1000000 0 ≤ ay < by ≤ 1000.

Todos los rectángulos son válidos (no existirán rectángulos de área cero).

Salida

Por cada caso de entrada, imprimir el número de caso seguido del número máximo de zombies que se pueden destruir con los disparos del cañón laser.

Ejemplo de Entrada

4
1
1 1 2 2
2
1 1 3 3
1 1 2 2
2
1 1 3 3
2 2 4 4
2
1 1 10000000 3
5000000 2 10000000 4

Ejemplo de Salida

Caso #1: 1
Caso #2: 4
Caso #3: 7
Caso #4: 2499998

Código

BOMBAZ

Intentos de resolución

23
5

Logrados

Etiquetas

#2012