teddy online judge

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

Ocurrió 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:

• Por cuestiones de urbanismo y para no destrozar ningún edificio, los muros estarán construidos sobre las banquetas de las calles, dispuestas en forma cuadricular
• Para simplificar el proceso de construcción, los muros serán rectangulares.
• Solo se tiene presupuesto para construir dos rectángulos para encerrar las áreas afectadas
• Los rectángulos no se deben intersectar. Esto es, ninguna manzana puede estar encerrada por más de un rectángulo

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