3428 - Triangulania

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3428 - Triangulania

Post by ymondelo20 » 4 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
isaac
Posts: 83
Joined: 4 years ago
Gender: None specified

Re: 3428 - Triangulania

Post by isaac » 4 years ago

Para este ejercicio hace falta tener en cuenta varios aspectos de la geometria y de las sucesiones. Por logica, se puede deducir que los tres puntos de dicho triangulo deben estar contenidos en el convex hull del conjunto de puntos. Una vez que se halla este poligono convexo, se pueden hacer las operaciones un poco mas rapido porque son muchos puntos menos que analizar, excepto para cuando los 1000 puntos del rango maximo, esten contenidos en este que ahi si hay que optimizar un monton.

La idea principal de dichas optimizaciones consisten en la siguiente idea. Si se toman a y b dos puntos cualesquiera del convex hull (nuestro nuevo conjunto) como base del triangulo y un tercer punto c, si desplazamos c por los diferentes puntos del convex hull en contra o a favor de las manecillas del reloj, podremos notar que el area del triangulo crece y luego decrece o viceversa. Esto pasa porque el conjunto de puntos antes mencionado es una sucesion unimodal respecto a las coordenadas x e y, respecto al area del triangulo antes mencionado como ejemplo y otras muchas cosas que cumplen con la caracteristica de ser unimodal. Esto nos da la ventaja de poder optimizar la solucion no teniendo que probar todos los trios posibles, sino hasta un limite. Por ejemplo, volviendo al caso anterior, supongamos que el punto c lo tomamos inicialmente por el que esta a continuacion del punto b y lo movemos en contra de las manecillas del reloj. Va a llegar hasta un punto en que el area va a ser maxima y luego va a decrecer. Cuando llegue a ese maximo, entonces actualizamos nuestra solucion y a quien movemos es a b. Vease que no hace falta volver a retomar la configuracion inicial para c respecto al nuevo valor de b porque siempre el maximo va a estar o en c o a continuacion de este.

Resumiendo el algoritmo, para todos los puntos hacemos lo siguiente:

1-> Tenemos el punto A que es el inicial.
2-> El punto B va a continuacion de A
3-> El punto C va a continuacion del B
4-> Vamos desplazando C hasta que el area del triangulo es maxima.
5-> Actualizamos nuestra solucion
6-> desplazamos B una vez
7-> Volvemos a (4).
8-> El punto B lo vamos desplazando tambien hasta que llega a un limite y ese limite esta (a diferencia del punto C respecto al area del triangulo) respecto a la distancia con el punto A. Vease que esta distancia tambien crece y luego decrece por lo que cuando comienza a decrecer no tiene sentido seguir analizando dichos triangulos.

Espero que lo hayan entendido (mas o menos) porque la solucion es un poco engorrosa. Cualquier duda, pregunten y yo respondo. Saludos!!!

Post Reply

Return to “Problem set”