2491 - Polygonal Lines
Oceania - South Pacific - 2002/2003

PDF

 

Submit

 

Ranking

 

Un rectángulo se corta por una secuencia de uno o más segmentos de línea recta que une un nodo de inicio a un nodo final, ambos por el borde del rectángulo.

Escribir un programa que lea los detalles del rectángulo y una línea divisoria, y determinar si el corte produce exactamente dos partes que podrían deslizarse mientras permanezcan en el mismo plano.

Los siguientes diagramas incluirán:

1. Varios casos en los que la respuesta es «sí», es decir, la línea de corte produce exactamente dos partes que pueden deslizarse lejos según sea necesario (1 - 5), y

2. Varios casos en los que la respuesta es «no», es decir, la línea de corte no produce exactamente dos partes según sea necesario (6 - 10).

\epsfbox{p2491.eps}

 

Diagrama (6) muestra dos piezas unidas que no pueden deslizarse. Diagramas (7 - 10) muestran cortes que producen tres partes en lugar de dos. Diagrama (7) muestra dos segmentos interceptados. Diagrama (8) muestra un nodo que toca otro segmento. Diagrama (9) muestra dos nodos que se superponen (en el punto más grueso). Diagrama (10) muestra dos segmentos que se superponen (a lo largo de la línea más gruesa). Esta superposición será más evidente en la muestra de entrada en la sección de abajo donde el tamaño de la cuadrícula se supone que es 10.

El programador que inicialmente recibió esta tarea cuenta de que si las dos partes pueden deslizarse, entonces siempre se podrán deslizar a lo largo de la ladera, de por lo menos uno de los segmentos de línea dados. Sin embargo, fue incapaz de poner a trabajar esta idea. Su tarea es ayudarlo y escribir el programa.

Input 

La entrada consta de una serie de casos. Cada caso comienza con un título seguido por tres enteros Xmax, Ymax, y N, separadas por espacios. El titulo del caso es una cadena de 1 a 20 letras, dígitos, y subrayados (sin espacios intermedios). Se supone que nuestro rectángulo está alineado con los ejes con el origen en la esquina inferior izquierda, y que Xmax y Ymax especifican la esquina superior derecha, donde 10 ≤ Xmax, Ymax ≤1000000. N representa el número de nodos de la línea de corte, 2 ≤ N ≤ 200000. Un solo `# 'en una línea que indica el final de la entrada.

Este título es la línea seguida por una o más líneas, según sea necesario para describir todos los nodos de la línea de corte, en la sucesión, 0, 1, 2 ,..., N - 1. Cada nodo contiene uno o más pares de números enteros no negativos, cada uno de los cuales las coordenadas x e y coordinan  el correspondiente nodo.

Se puede suponer que:

Output 

La salida se compone de una línea para cada caso. Hay dos alternativas:

La línea de corte se reúne todos los requisitos y produce exactamente dos partes que pueden deslizarse. En este caso asumimos que ((x1, y1), (x2, y2)) es el primero de los segmentos de línea cuya pendiente se puede utilizar además para deslizar las dos partes. La salida del título del caso, seguido de dos puntos (`:'), un espacio ( «»), la palabra «yes», otro espacio ( ` ') y, a continuación, los cuatro enteros x1, y1, x2, y2, separados por espacios (estas coordenadas deben aparecer en su secuencia de entrada).

De lo contrario la salida del título del caso, seguido de dos puntos (`:'), un espacio ( «»), y la palabra «no».

Sample Input 

Case_1 30 40 2

0 20 30 20

Case_2 30 40 3

30 20 20 20 0 20

Case_3 30 40 4

0 10 20 20 10 30 10 40

Case_4 30 40 6

20 40 10 20 10 10

20 20 20 10 10 0

Case_5 30 40 4

20 40 20 20 10 20 10 40

Case_6 30 40 6

10 0 10 10 20 10 20 30 10 20 10 40

Case_7 30 40 6

10 0 10 10 20 20 20 10 10 20 10 40

Case_8 30 40 5

10 0 10 25 20 10 20 20 0 30

Case_9 30 40 6

10 0 10 20 20 10 20 20 10 20 10 40

Case_10 30 40 7

10 40 10 20 20 20 20 10 10 10 10 30 0 30

#

Sample Output 

Case_1: Yes 0 20 30 20

Case_2: Yes 30 20 20 20

Case_3: Yes 0 10 20 20

Case_4: Yes 10 10 20 20

Case_5: Yes 20 40 20 20

Case_6: No

Case_7: No

Case_8: No

Case_9: No

Case_10: No

 

South Pacific 2002-2003

 

Traducido por: Piero Esthéfano Sánchez Vásquez