3229 - Robot

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:

3229 - Robot

Post by ymondelo20 » 5 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: 3229 - Robot

Post by isaac » 4 years ago

La idea fundamental es buscar el Convex Hull y luego ver, para cada lado de ese poligono, buscar cual es el punto que esta mas alejado (el cual obviamente pertenece al convex hull). Luego se toman de entre todas esas distancias, la menor. El problema esta en que son 10000 puntos y si por casualidad algun tc los tiene a los 100000 como parte del CH, entonces representa un problema realmente si no se tiene en cuenta una idea basica de la geometria computacional para este tipo de problemas. Suerte!!.

User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3229 - Robot

Post by ymondelo20 » 4 years ago

Creo que ese problema es equivalente a uno que salió en la Final Mundial del ACM-ICPC en Orlando (2011)...
https://icpcarchive.ecs.baylor.edu/inde ... oblem=3139
Para resolverlo, se deben chequear otros elementos además de los puntos más alejados... es en realidad un poco trickly, y lleva rotaciones, y mucho trabajo con segmentos.

@Isaac: me suena a que debes revisar si los JD fueron creados correctamente :idea:
"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: 3229 - Robot

Post by isaac » 4 years ago

Brother, hice un seguimiento y no tienen ningun problema. Si tienen alguna sugerencia respecto a algun codigo que crean que es la solucion correcta y me lo pueden hacer llegar seria un poco mas seguro para detectar si realmente el problema es de una de las dos partes. Mi correo es isaacv@fecrd.cujae.edu.cu.

User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3229 - Robot

Post by ymondelo20 » 4 years ago

Veré qué hago, porque revisarlo lleva su tiempo.
"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: 3229 - Robot

Post by isaac » 4 years ago

Si quieres te envio la solucion oficial a tu correo comentada para que sea mas rapido el proceso de revision y verifiques si tiene o no algun bug.

User avatar
WIL
Posts: 11
Joined: 8 years ago
Gender: Male

Re: 3229 - Robot

Post by WIL » 4 years ago

Este problema es una variante del problema http://coj.uci.cu/24h/problem.xhtml?pid=3096, con la diferencia de lo que se pide. Sería bueno revisar lo JD, porq mi sol con ExtremePoint me está dando wa prueba 1.
I'm interesting in learn!!!

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

Re: 3229 - Robot

Post by isaac » 4 years ago

¿En qué consiste ExtremePoint? Nunca había escuchado ese término. Quizás lo maneje, pero no lo he visto nunca formalmente.

User avatar
WIL
Posts: 11
Joined: 8 years ago
Gender: Male

Re: 3229 - Robot

Post by WIL » 4 years ago

isaac wrote:¿En qué consiste ExtremePoint? Nunca había escuchado ese término. Quizás lo maneje, pero no lo he visto nunca formalmente.
Es un algoritmo en geometría computacional que consiste en de forma logaritmica buscar sobre un poligono convexo el punto más alejado en una dirección (vector dirección). Para más información puedes documentarte aquí. La idea de usar este algoritmo para resolver el problema, es en ecencia, que el minimo rectágulo que recubre un polígono convexo, siempre va a tener un lado adyacente a dicho poligono convexo (demostración de esto aquí) por tanto recorriendo cada lado del poligono convexo y hallando los puntos extremos que formarían al rectángulo de recubrimiento pues se resuelve el problema q señalé antes y el q propones, e incluso se puede determinar hasta el cuadrado de recubrimiento mínimo si se busca el menor de todos los lados de cada rectángulo de recubrimiento hallado.
I'm interesting in learn!!!

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

Re: 3229 - Robot

Post by isaac » 4 years ago

Men,en esencia es eso, buscar el máximo entre las distancias máximas relativas a cada segmento del convex hull.

Post Reply

Return to “Problem set”