Module: Geometría


Problem

5 /7


Recoger maestro

Theory Click to read/hide

Intersección

Punto de intersección de líneas

a1, b1, c1 - coeficientes de la primera línea,
a2, b2, c2 - coeficientes de la segunda línea,
x, y - punto de intersección.

\(x = {-(c1 \cdot b2 - c2 \cdot b1) \over (a1 \cdot b2 - a2 \cdot b1)} \\ y = {-(a1 \ cdot c2 - a2 \cdot c1) \over (a1 \cdot b2 - a2 \cdot b1)} \)

Ya sabemos cómo verificar la intersección de las líneas (no son paralelas) y encontrar su punto de intersección.

Ahora, aprendamos a hacer esto con segmentos. 

Primero, aprendamos cómo simplemente verificar si hay intersección.

Los segmentos se intersecan si los extremos de uno están en lados opuestos del otro y viceversa (esto se comprueba fácilmente mediante el producto vectorial).  El único caso en el que esto no funcionará: los segmentos se encuentran en una línea recta. Para ello, debe verificar la intersección de los llamados. cuadro delimitador (cuadro delimitador del segmento): compruebe la intersección de la proyección de los segmentos en X e Y.

ejes.

Ahora que sabemos cómo verificar la intersección de los segmentos, aprendamos cómo encontrar el punto (o segmento) de su intersección:
- si no se cruzan, entonces está claro que tal punto no existe;
- de lo contrario, construiremos líneas rectas en las que se encuentran estos segmentos.

Si son paralelos, entonces los segmentos se encuentran en la misma línea y necesitamos encontrar el segmento de intersección, desde el máximo de los bordes izquierdos de los segmentos hasta el mínimo de los bordes derechos (el el punto es menor que el otro punto, si está a la izquierda, en caso de igualdad X-coordenadas - si es más bajo).

Si las líneas no son paralelas, encuentre el punto de su intersección y devuélvalo.

Problem

Venceslav leyó recientemente un nuevo libro de camionetas y ahora quiere poner a prueba sus conocimientos en el parque. Para simplificar, imaginemos el parque como un conjunto de caminos, que son segmentos en un plano. Wenceslao ya ha caminado por este parque, y sabe qué chica camina por qué camino. El problema es que Wenceslao es muy perezoso y solo camina por un camino. Y también es demasiado perezoso para averiguar qué tipo de chicas puede encontrar en el camino, y por eso te pidió a ti, su mejor amigo, que lo ayudaras en este difícil asunto.
 
Entrada
La primera línea contiene las coordenadas de los extremos de la ruta (X1, Y1) y ( X2, Y2), por donde camina Wenceslao (\(- 20 <= X1, Y1, X2, Y2 <= 20\)).
La segunda línea contiene un número entero N: el número de caminos por los que caminan las niñas (\(0 <= N <= 5\) ).
En las siguientes líneas N, ingrese las coordenadas de los extremos de los caminos por donde caminan las niñas (Xi1, Yi1< /sub>) y (Xi2, Yi2 ), por i-th path caminando i-th girl (\(-20 <= X_{i1}, Y_ {i1}, X_{i2}, Y_{i2} <= 20\))
 
Salida
En la primera línea, escriba el número M: el número de niñas cuyos caminos se cruzarán con el camino de Wenceslao (tocar los caminos se considera una intersección).
En la segunda línea, escriba números M: números de chicas que nuestro héroe conocerá. ¡Las chicas se numeran a partir del uno!
 
Ejemplos

 

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Entrada Salida
1
0 0 2 2
1
0 2 2 0
 1
1