Geometra para ICPC

Training Camp Argentina 2013

Fidel I. Schaposnik (UNLP) - fidel.s@[Link]

19 de julio de 2013

Contenidos

Introduccion
Representacion de objetos fundamentales
Puntos y vectores
Lneas y segmentos

Problemas lineales en geometra computacional

Ecuaciones implcitas
Intersecci
on de planos en 3D

Tecnicas de barrido
A Safe Bet
November Rain

Problemas para practicar

Training Camp Argentina 2013

Geometra para ICPC

Introduccion
En qu
e consiste un problema de geometra computacional?
Generalmente, los problemas de geometra en el ICPC requieren
calcular alguna cantidad (e.g. distancia, area, parametros optimos
para una configuracion determinada, etc) relacionada con
elementos geometricos como puntos, lneas, crculos, y demas. La
solucion de un problema de geometra involucra dos pasos:
1

Representar los objetos geometricos involucrados en el

problema, de modo de poder operar con ellos.

Desarrollar un algoritmo utilizando lo anterior para calcular la

respuesta buscada.

Para poder dedicarnos a la parte interesante, debemos primero

asegurarnos de que el primer punto no es un impedimento.

Training Camp Argentina 2013

Geometra para ICPC

Introduccion (cont.)
A FAVOR: Podemos visualizar los algoritmos facilmente.
EN CONTRA: Debemos evitar nuevos tipos de problemas (errores
numericos, casos degenerados, c
odigo mas largo, etc).

Training Camp Argentina 2013

Geometra para ICPC

Introduccion (cont.)
A FAVOR: Podemos visualizar los algoritmos facilmente.
EN CONTRA: Debemos evitar nuevos tipos de problemas (errores
numericos, casos degenerados, c
odigo mas largo, etc).
Antes de empezar, algunas consideraciones generales
A lo largo de esta clase nos vamos a concentrar casi
exclusivamente en problemas de geometra en 2D.
La pr
actica y las buenas costumbres son todava mas
importantes que en los problemas convencionales.
Los problemas de geometra muchas veces sirven para
distinguir a los buenos equipos de los excelentes!

Training Camp Argentina 2013

Geometra para ICPC

Puntos y vectores
Un punto en el plano (o un vector desde el origen hasta dicho
punto) se puede representar con un par ordenado de coordenadas
en un sistema cartesiano:
~ = (x, y )
P
con
x, y R
Algunas operaciones entre vectores
La suma y resta de vectores se realiza componente a
componente:
~ =P
~1 P
~2
P

(x, y ) = (x1 x2 , y1 y2 )
p
~ = x 2 + y 2.
La longitud o norma de un vector es |P|
~1 y P
~ 2 es |P
~1 P
~ 2|
La distancia eucldea entre dos puntos P
El producto escalar de dos vectores es un n
umero, y se define
como
~1 P
~ 2 := x1 x2 + y1 y2 = |P
~ 1 ||P
~ 2 | cos
P
Observar que es la proyecci
on de un vector sobre otro, y en
particular si = 90 el producto escalar se anula.
Training Camp Argentina 2013

Geometra para ICPC

Puntos y vectores (cont.)

El producto vectorial de dos vectores es un vector en la
direccion normal al plano generado por ellos. En dos
dimensiones nos puede interesar su u
nica componente no nula,


~1 P
~ 2 = x1 y2 x2 y1 P
~1 P
~2
P
z

Observar que
~1 P
~ 2 | = |P
~ 1 ||P
~ 2 | sin ,
|P
es decir el area del paralelogramo formado por los vectores y
sus traslaciones paralelas.
En particular si = 0
o = 180 el producto vectorial se
anula.

Training Camp Argentina 2013

Geometra para ICPC

Puntos y vectores (codigo.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

s t r u c t pt {
double x , y ;
p t ( d o u b l e xx = 0 . 0 , d o u b l e yy =0.0) { x=xx ; y=yy ; }
};
p t o p e r a t o r +( c o n s t p t &p1 , c o n s t p t &p2 ) {
r e t u r n p t ( p1 . x+p2 . x , p1 . y+p2 . y ) ; }
p t o p e r a t o r ( c o n s t p t &p1 , c o n s t p t &p2 ) {
r e t u r n p t ( p1 . xp2 . x , p1 . yp2 . y ) ; }
d o u b l e o p e r a t o r ( c o n s t p t &p1 , c o n s t p t &p2 ) {
r e t u r n p1 . x p2 . x + p1 . y p2 . y ; }
d o u b l e o p e r a t o r ( c o n s t p t &p1 , c o n s t p t &p2 ) {
r e t u r n p1 . x p2 . y p1 . y p2 . x ; }
d o u b l e norm ( c o n s t p t &p ) { r e t u r n s q r t ( pp ) ; }
d o u b l e d i s t ( c o n s t p t &p1 , c o n s t p t &p2 ) {
r e t u r n norm ( p1p2 ) ; }

Estructura y operaciones elementales con puntos

Training Camp Argentina 2013

Geometra para ICPC

Lneas y segmentos
Una lnea o un segmento se pueden representar de varias formas
distintas:
~1 y P
~ 2 sobre la lnea (los extremos del
Con dos puntos P
segmento)
~ 0 sobre la lnea y un vector director V
~
Con un punto P
Mediante una ecuaci
on implcita ax + by + c = 0.
Se puede pasar de una a otra representaci
on trivialmente, y la
eleccion de una u otra depende en definitiva del uso que se vaya a
darle.
n
o
~
~
La representacion P0 , V se conoce como parametrica, porque
nos permite recorrer todos los puntos de la lnea o segmento con
(
tR
lnea
~
~ 0 + tV
~
P(t)
=P
con
t [0, 1] segmento
Training Camp Argentina 2013

Geometra para ICPC

Lneas y segmentos (cont.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

struct line {
double a , b , c ;
l i n e ( d o u b l e aa = 0 . 0 , d o u b l e bb = 0 . 0 , d o u b l e c c =0.0) {
a=aa ; b=bb ; c=c c ;
}
};
d o u b l e d i s t ( c o n s t p t &p , c o n s t l i n e & l ) {
r e t u r n ABS( l . a p . x+l . bp . y+l . c ) / s q r t (SQ( l . a )+SQ( l . b ) ) ; }
line

l i n e p p ( c o n s t p t &p1 , c o n s t p t &p2 ) {
r e t u r n l i n e ( p2 . yp1 . y , p1 . xp2 . x , p2 p1 ) ; }

line

l i n e p e r p p ( c o n s t l i n e &l , c o n s t p t &p ) {
r e t u r n l i n e ( l . b , l . a , l . bp . x l . a p . y ) ; }

line

m e d i a t r i z ( c o n s t p t &p1 , c o n s t p t &p2 ) {
r e t u r n l i n e p e r p p ( l i n e p p ( p1 , p2 ) , ( p1+p2 ) / 2 . 0 ) ; }

Ejemplo de uso de la representaci

on implcita

Training Camp Argentina 2013

Geometra para ICPC

Lneas y segmentos (cont.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

line

b i s e c t r i z ( c o n s t p t &p1 , c o n s t p t &pc , c o n s t p t &p2 ) {

p t pc1 = p1pc , pc2 = p2pc ;
i f (ABS( pc1 pc2 ) < EPS ) {
i f ( pc1 pc2 > ZERO) r e t u r n l i n e p p ( pc , p1 ) ;
e l s e r e t u r n l i n e p e r p p ( l i n e p p ( p1 , p2 ) , pc ) ;
}
r e t u r n l i n e p p ( pc , pc+( pc1 / norm ( pc1 )+pc2 / norm ( pc2 ) ) / 2 . 0 ) ;

}
int

i n t e r l l ( c o n s t l i n e &l 1 , c o n s t l i n e &l 2 , p t &p ) {

d o u b l e d e t = l 1 . a l 2 . b l 1 . b l 2 . a ;
i f (ABS( d e t ) < EPS ) {
i f (ABS( l 1 . a l 2 . c l 1 . c l 2 . a ) < EPS ) r e t u r n 1;
else return 0;
}
p . x = ( l 1 . b l 2 . c l 2 . b l 1 . c ) / d e t ;
p . y = ( l 2 . a l 1 . c l 1 . a l 2 . c ) / det ;
return 1;

Ejemplo de uso de la representaci

on implcita (cont.)
Training Camp Argentina 2013

Geometra para ICPC

Problemas lineales en geometra computacional

A veces aparecen sistemas de ecuaciones en problemas de
geometra computacional: Joes Triangular Gardens (NA-GNY08)
pide hallar la elipse tangente a un triangulo en los puntos medios
de sus lados:

Training Camp Argentina 2013

Geometra para ICPC

Problemas lineales en geometra computacional

A veces aparecen sistemas de ecuaciones en problemas de
geometra computacional: Joes Triangular Gardens (NA-GNY08)
pide hallar la elipse tangente a un triangulo en los puntos medios
de sus lados:

Una elipse queda definida por ax 2 + bxy + cy 2 + dx + ey + f = 0

con b 2 4ac < 0, de modo que tenemos 5 parametros que definen
la elipse (a, b, c, d, e y f , a menos de una normalizacion).
Training Camp Argentina 2013

Geometra para ICPC

Problemas lineales en geometra computacional (cont.)

~ m = (x m , y m ) con i = 1, 2, 3 son los puntos medios de los
Si P
i
i
i
lados del triangulo, tenemos 3 ecuaciones de interseccion
a(xim )2 + b xim yim + c(yim )2 + d xim + e yim + f = 0
y 2 ecuaciones de tangencia (derivando implcitamente para dos
lados no verticales)
2a xim +b(yim +xim y 0 (xim , yim ))+2c yim y 0 (xim , yim )+d+ey 0 (xim , yim ) = 0
Los valores de las derivadas son simplemente las pendientes de los
i
correspondientes lados del trangulo: y 0 (xim , yim ) = y
xi .

Training Camp Argentina 2013

Geometra para ICPC

Problemas lineales en geometra computacional (cont.)

~ m = (x m , y m ) con i = 1, 2, 3 son los puntos medios de los
Si P
i
i
i
lados del triangulo, tenemos 3 ecuaciones de interseccion
a(xim )2 + b xim yim + c(yim )2 + d xim + e yim + f = 0
y 2 ecuaciones de tangencia (derivando implcitamente para dos
lados no verticales)
2a xim +b(yim +xim y 0 (xim , yim ))+2c yim y 0 (xim , yim )+d+ey 0 (xim , yim ) = 0
Los valores de las derivadas son simplemente las pendientes de los
i
correspondientes lados del trangulo: y 0 (xim , yim ) = y
xi .
Si resolvemos el sistema de 5 ecuaciones con 5 incognitas, la
solucion al problema esta practicamente dada.
Training Camp Argentina 2013

Geometra para ICPC

Problemas lineales en geometra computacional (cont.)

Otro ejemplo: consideremos la intersecci
on de dos planos en tres
dimensiones.

Training Camp Argentina 2013

Geometra para ICPC

Problemas lineales en geometra computacional (cont.)

Otro ejemplo: consideremos la intersecci
on de dos planos en tres
dimensiones.
Un plano se define con un punto P~0 contenido en el plano y un
~ 0 ortogonal al mismo. Todos los otros puntos satisfacen
vector N
~ P
~ 0) N
~0 = 0
(P
lo cual conduce a la ecuaci
on mas familiar
ax + by + cz + d = 0

~ 0 = (a, b, c)
para N

~0 N
~0
d = P

~ 1, N
~ 1 } y {P
~ 2, N
~ 2 } se
En general, dos planos definidos por {P
intersecan para dar una lnea. C
omo la hallamos?

Training Camp Argentina 2013

Geometra para ICPC

Otros problemas lineales (cont.)

Usamos la representaci
on parametrica de la lnea, de modo que
~
~.
buscamos un punto P sobre ella y un vector director V

Training Camp Argentina 2013

Geometra para ICPC

Otros problemas lineales (cont.)

Usamos la representaci
on parametrica de la lnea, de modo que
~
~.
buscamos un punto P sobre ella y un vector director V
Nuestra lnea debe pertenecer a ambos planos, luego es ortogonal
~1 y N
~ 2 . Entonces
a los vectores N
~ =N
~1 N
~2
V
~ = ~0, los planos son paralelos y no hay interseccion entre ellos.
Si V
~
C
omo hallamos P?

Training Camp Argentina 2013

Geometra para ICPC

Otros problemas lineales (cont.)

Usamos la representaci
on parametrica de la lnea, de modo que
~
~.
buscamos un punto P sobre ella y un vector director V
Nuestra lnea debe pertenecer a ambos planos, luego es ortogonal
~1 y N
~ 2 . Entonces
a los vectores N
~ =N
~1 N
~2
V
~ = ~0, los planos son paralelos y no hay interseccion entre ellos.
Si V
~
C
omo hallamos P?
~ el punto sobre la lnea que esta mas cerca de cierto punto
Sea P
~ = (x, y , z) minimiza
fijo y arbitrario (e.g. el origen). Entonces P
D2 = x2 + y 2 + z2
mientras esta en ambos planos, i.e. satisfaciendo




~ P
~1 N
~1 = 0 y
~ P
~2 N
~2 = 0
P
P
Training Camp Argentina 2013

Geometra para ICPC

Otros problemas lineales (cont.)

~ minimizando D 2 bajo estas
Podemos hallar el punto P
restricciones, usando multiplicadores de Lagrange. Definimos




~ P
~ 2 N
~2
~ P
~ 1 N
~ 1 +2 P
f (x, y , z, 1 , 2 ) = x 2 +y 2 +z 2 +1 P
Luego debemos exigir
f
f
f
= 2x+1 xN1 = 0
= 2y +1 yN1 = 0
= 2z+1 zN1 = 0
x
y
z




f
f
~ P
~1 N
~1 = 0
~ P
~2 N
~2 = 0
= P
= P
1
2

Training Camp Argentina 2013

Geometra para ICPC

Otros problemas lineales (cont.)

~ minimizando D 2 bajo estas
Podemos hallar el punto P
restricciones, usando multiplicadores de Lagrange. Definimos




~ P
~ 2 N
~2
~ P
~ 1 N
~ 1 +2 P
f (x, y , z, 1 , 2 ) = x 2 +y 2 +z 2 +1 P
Luego debemos exigir
f
f
f
= 2x+1 xN1 = 0
= 2y +1 yN1 = 0
= 2z+1 zN1 = 0
x
y
z




f
f
~ P
~1 N
~1 = 0
~ P
~2 N
~2 = 0
= P
= P
1
2
O, en notacion matricial

0
2
0
0 xN1 xN2
x
0
0
2
0 yN1 yN2

0
2 zN1 zN2

z = 0
~
~
xN yN zN

0
0
1
P1 N1
1
1
1
~2 N
~2
xN2 yN2 zN2 0
0
2
P
Training Camp Argentina 2013

Geometra para ICPC

Tecnicas de barrido: A Safe Bet

Training Camp Argentina 2013

Geometra para ICPC

Tecnicas de barrido: November Rain

Training Camp Argentina 2013

Geometra para ICPC

Problemas para practicar

In-circles Again - LA 4714

Shortest Flight Path - LA 6035
Coverage - LA 4562
Malfatti Circles - LA 4642
Onion Layers - LA 3655
Deer-Proof Fence - LA 4450
Watering Plants - GCJ 2009, Round 2
High Mountains - SPOJ TAP2012H
Garden Fence - LA 5795

Training Camp Argentina 2013

Geometra para ICPC

Gracias!

Training Camp Argentina 2013

Geometra para ICPC