One interesting geometry problem...... Help me to solve it

maratkalibek · Post by **maratkalibek** » Tue Oct 07, 2003 8:26 pm

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.

Maarten · Post by **Maarten** » Tue Oct 07, 2003 11:25 pm

what you mean by "segments" ?

maratkalibek · Post by **maratkalibek** » Wed Oct 08, 2003 3:41 am

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.

Moni · Post by **Moni** » Wed Oct 08, 2003 8:17 am

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???

maratkalibek · Post by **maratkalibek** » Wed Oct 08, 2003 8:47 am

No, it is convex polygon with n sides.

alex[LSD] · Post by **alex[LSD]** » Sun Feb 01, 2004 12:56 pm

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.

titid_gede · Post by **titid_gede** » Mon Feb 02, 2004 4:24 pm

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-

alex[LSD] · Post by **alex[LSD]** » Mon Feb 02, 2004 8:26 pm

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.

titid_gede · Post by **titid_gede** » Tue Feb 03, 2004 6:59 am

thanks, i got it

-titid-

Cosmin.ro · Post by **Cosmin.ro** » Wed Feb 04, 2004 12:41 am

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

alex[LSD] · Post by **alex[LSD]** » Wed Feb 04, 2004 12:47 pm

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

Cosmin.ro · Post by **Cosmin.ro** » Thu Feb 05, 2004 12:37 am

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.

alex[LSD] · Post by **alex[LSD]** » Thu Feb 05, 2004 6:40 pm

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?

Cosmin.ro · Post by **Cosmin.ro** » Sat Feb 07, 2004 12:50 pm

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)

OJ Board

One interesting geometry problem...... Help me to solve it

One interesting geometry problem...... Help me to solve it

Re: One interesting geometry problem......