Fork me on GitHub

teddy online judge

teddy es un oso de peluche

51. Toxicity

Limite de tiempo : 2 seg.   Total runs : 38  Aceptados : 8

More wood for the fires, loud neighbors
Flashlight reveries caught in the headlights of a truck
Eating seeds as a pastime activity
The toxicity of our city, of our city
— System of a Down, Toxicity

ejemploOcurrió un accidente en una planta que trabaja con químicos peligrosos y ahora varias zonas de la ciudad donde habitas están cubiertas por desechos tóxicos. Tú, como asistente personal al alcalde de la ciudad, quieres ayudar a las labores de contención del accidente.

Una vez que los habitantes de las zonas afectadas han sido evacuados, se necesita construir un cerco de contención hecho de plomo y concreto alrededor de los puntos contaminados para evitar que la contaminación se siga esparciendo. Obviamente, la gente de la ciudad no está muy contenta con que se construyan muros de contención, pues obstruirá el acceso a sus casas o trabajos, así que tu misión es garantizar la seguridad de la ciudad minimizando el área encerrada.

Existen algunos requisitos que la ciudad ha puesto para poder construir los muros, así que tienes que tomarlos en consideración:

Input

La primer línea de la entrada contiene un único número, N (1 ≤ N ≤ 30), el número de casos de prueba que siguen. Cada caso contiene un entero n (2 ≤ n ≤ 20,000), seguido de n líneas. Cada línea contiene dos enteros x y y (0 ≤ x, y ≤ 32,000) separados por un espacio, que indican las coordenadas de la manzana donde se encuentra un edificio dañado que debe ser cercado. Puede haber más de un edificio dañado por manzana.

Output

Para cada caso, debes imprimir una línea "Caso c: n", siendo c el número secuencial del caso y n el menor número posible de manzanas encerradas, tal que usando dos rectángulos disjuntos, puedas encerrar todos los edificios dañados.

Sample Input/Output

2
7
1 5
3 3
3 5
5 1
6 5
5 1
3 2
8
1 1
2 1
3 1
4 1
1 4
2 4
3 4
4 4
Caso 1: 15
Caso 2: 8

Hecho por Alan Gonzalez @_alanboy ; Concepto Luis Hector Chavez @lhchavez ; Infraestructura por Instituto Tecnologico de Celaya

contribuciones de los usuarios bajo la licencia cc-wiki con atribucion requerida