OJ Board

Here it is.
If you had n segments on plane, from which you can construct a polygon. Find algorithm to construct polygon with maximal area.

what you mean by "segments" ?

I mean "line segments", sorry but I don't know how to express it in other words in English. You can assume that we always can construct a polygon from this line segments.

maratkalibek wrote:Here it is.
If you had n segments on plane, from which you can construct a polygon. Find algorithm to construct polygon with maximal area.

Can there be any loop inside polygon? I mean is there any line segment intersect?

Or it will be a convex polygon???

No, it is convex polygon with n sides.

OK there is such a problem on Timus site.
The idea of solving it is that the area of a poligon is maximum when there can be a circle drawn around it. I dont know how to prove that. Well circle is a curve that provides maximum area for a given perimeter, so you are kinda building a polygon as "close" as possible to a circle.
So basicly it doesnt matter in what order you connect the segments. All you need to find is radius R. You can use binary search for that.

P.S. There was case i needed tto consider - when one side was pretty long and the rest were pretty short.
For example
3
5.0
2.6
2.6
I think there were some tricks about these cases.

So basicly it doesnt matter in what order you connect the segments. All you need to find is radius R. You can use binary search for that.

how to find radius R? we dont have any clues other than the lengths of line segments.

-titid-

To find R use binary search.

Lets say you are trying a current value of R = Rcur.

If our poligon has the circle drawn around it we have N triangles with Sides

[ RCur, RCur, A(i)A(i+1) ] you need to find angles between RCur and RCur and SUM THEM UP. If the sum is less then 2*pi then RCur is too big for our set of segments, otherwise R>=RCur. (And dont forget the tricky case, you ll need to make sure you re calculating the angle right).

Thats the condition you ll need to use in binary search.

thanks, i got it

-titid-

Thanks for spoiling the current task from the http://www.ginfo.ro/contest, I hope you will be able to implement it ...

Sorry , just didnt know bout that contest.

P.S. Are you THAT Narugesi Cosmin who helped me with Questions and Answers on Timus? (1099 or 1098) Thanks again if so

Negruseri Cosmin, I don't remember helping you but if I did I'm glad, you didn't spoil the problem, the one who asked for help here did, and I'm a little sad becose I'm the problem setter.

Sorry to misprint your name.
You sure did help me that time, Negruseri. Btw, how did you prove that such a polygon has the maximum area?

I found a paper of Djikstra wich proves it with arguments from phisics (you can find it here http://www.cs.utexas.edu/users/EWD/index06xx.html document 693)