Cómo calcular el área común entre cículos?

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
User avatar
WIL
Posts: 11
Joined: Thu Dec 08, 2011 12:02 pm
Gender: Male

Cómo calcular el área común entre cículos?

Postby WIL » Thu Nov 20, 2014 8:54 pm

Creo que este es un problema que salió recientemente en una de las competencias pasadas de la ACM, pero luego de buscar en varios lugares, no he encontrado una solución entendible y práctipa para calcular, dados N círculos en un plano, el área común que estos tienen.
Leyendo en codeforces, me encontré una posible solución, donde la idea es hacer líneas verticales en cada intersección entre un par de círculos, para luego calcular el área que se encuentra en estas regiones. Bueno esto no se si es concluyente, pero aun no he dado con una solución a partir de ello.
Gracias de antemano!!! :?:


I'm interesting in learn!!!

User avatar
ymondelo20
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: Cómo calcular el área común entre cículos?

Postby ymondelo20 » Fri Nov 21, 2014 10:53 am

Entre dos círculos es solo algunas fórmulas no muy complicadas.

Ya para un conjunto de círculos no es algo sencillo, aunque presumo que debe poder resolverse (con algunas complicaciones obvio) usando un barrido de plano.
Algunos acercamientos interesantes sobre el tema los puedes ver en los tutoriales de TopCoder http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index y específicamente en el que se titula "Line Sweep Algorithms" donde se menciona un problema equivalente pero con rectángulos en lugar de círculos.

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

User avatar
WIL
Posts: 11
Joined: Thu Dec 08, 2011 12:02 pm
Gender: Male

Re: Cómo calcular el área común entre cículos?

Postby WIL » Fri Nov 21, 2014 1:08 pm

Si bueno, ya ese tema lo he visto, he incluso he aceptado dos problemas del coj sobre ese tema (1999,2000), y complicando un poco más la cosa, lo llevé a un barrido en 3d, para dar solución al problema 1008. Pero con los cículos, se me hace muy complejo calcular el área en cada una de las secciones, cuando se está realizando el barrido de planos. De todas formas voy a revisar bien el TopCoder, que ahí siempre hay buenos tutos, y ver si encuentro algo al respecto!!!
I'm interesting in learn!!!


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest