ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1058. Chocolate

At last I have solved it!!! There is my solution
Posted by Виктор (marilyn_manson@bk.ru) 21 Jun 2004 21:38
My decision:

1.) We consider polygon such what it is, we spend 2 straight linees in parallel OX, one passes through the lowermost point, another through the uppermost. We spend a third - a line of a break on middle between a theme to two. We look at fragments. If the area of the top fragment is more, then we lift a line of a break on 1/4 all intervals, else is lowered. Then shift on 1/8 etc. To put it briefly, binary search we find height of a horizontal that it divided into equal fragments.

2.) We turn a figure, concerning any fixed point on a small corner (about 0.01 radian)

3.) We carry out action number 1.

And so we shall consider all possible variants. Certainly sooner or later it is necessary to stop to rotate a figure. It at turn on 180 degrees from an initial arrangement of a figure.

My decision works for 0.078 seconds and 253 Kb.

GOOD LUCK!

I am sorry for bad English
Hm-m-m (+)
Posted by Dmitry 'Diman_YES' Kovalioff 21 Jun 2004 22:21
My solution differs from yours one, but I think your idea is interesting. I've solved it in a classical way using 2 binary searches - the first one inside the second, and then just a constants optimization...
Re: Hm-m-m (+)
Posted by Виктор (marilyn_manson@bk.ru) 21 Jun 2004 23:02
Thank for good words :-)
Can you explain your method for me? You know my email.

Edited by author 21.06.2004 23:05
Re: Hm-m-m (+)
Posted by Denis Koshman 20 Aug 2008 20:13

Edited by author 20.08.2008 20:22
Hm-hm-hm
Posted by Dmitry "Logam" Kobelev [TSOGU] 9 Jan 2009 00:41
I used similar idea and checked 10000 angles, but had wa10. Then I replaced it into 1000 and got AC. Now i'm wonder why, it seems to me accuracy lowered then.