OJ Board

Given some lengths, can we create a closed polygon with them?

What is the complexity of such algorithm if one exist?


E.g: Given 4, 4, 4, 4 we can build a square...

I believe it's always possible if only the longest edge is shorter than sum of all others.

Yes, what Krzysztof said is right, you can always create it, if longest edge < sum of the other edges.

This was one of the problems of this years Baltic Olympiad of Informatics. One Solution to find such a polygon is to put all the points on a circle and do a binary search over the radius. You can then calculate the arc each edge takes in the circle and if they add up to 360 degrees, you found a solution.

Its always possible to put them on a circle, cause you can always create such a polygon with the above algorithm...

Thank you very much..

Will that work for any number of edges? I mean not just poylgons with 4 sides..

Yes that will work for any number of edges greater than 2

GeorgeBusch wrote:Yes that will work for any number of edges greater than 2

If you have just 2 edges, the longest one in never shorter then sum of the others (actually the shorter edge). Thus the condition works even for 2

Is there an algorithm that searches for such a polygon.. if one exists?

Zyaad Jaunnoo wrote:Is there an algorithm that searches for such a polygon.. if one exists?

What's wrong with the algorithm GeorgeBusch's described?