teddy online judge

28. Ligas

Limite de tiempo : 1 seg.   Total runs : 131  Aceptados : 42

Tu hermano pequeño y tú tienen un juego bastante curioso. Tu abuela les regaló una tabla con clavos dispuestos en una matriz cuadrangular y unas ligas. Tu hermano y tú se turnan colocando ligas de la siguiente manera: seleccionan dos clavos y estiran la liga para que los extremos de la liga se sostengan con ellos. El chiste del juego es que las ligas que coloquen nunca se intersecten ni toquen. El primer jugador que no pueda colocar su liga es el que pierde.

Tú como buen programador decides hacer un programa para que tu hermanito se entretenga. Tu programa coloca una liga al azar y espera a que tu hermano coloque la suya. Ahora debes verificar si tu hermano colocó la liga en un lugar válido.

Entrada

La primer línea del programa contiene un entero k (1 ≤ k ≤ 100) con el número de casos de prueba. Cada caso de prueba contiene la descripción de las dos ligas. Cada liga se puede representar con dos pares de coordenadas enteras x1, y1, x2, y2 (0 ≤ xi, yi ≤ 1000) que representan el punto de inicio y final de la liga.

Salida

Para caso de prueba debes escribir una línea de texto con el mensaje "Caso k: No hay interseccion." si las ligas no se intersectan o "Caso k: Hay interseccion.", si las ligas se intersectan. k es el número de caso de prueba (están numerados secuencialmente, empezando por 1). No escribas el acento de intersección.

Entrada de Prueba

2
1 4 5 2 3 4 7 8
1 4 5 2 1 2 7 8

Salida de Prueba

Caso 1: No hay interseccion.
Caso 2: Hay interseccion.