How to solve the problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

How to solve the problem

Post by windows2k » Fri May 14, 2004 5:34 am

Workers are going to enclose a new working region with a fence. For their convenience the enclosed area has to be as large as possible. They have N rectangular blocks to build the fence. The length of the i-th block is Li meters. All blocks have the same height of 1 meter. The workers are not allowed to break blocks into parts. All blocks must be used to build the fence.


Input

The first line of the input file contains one integer N (3 <= N <= 100).

The following N lines describe fence blocks. Each block is represented by its length in meters (integer number, 1 <= Li <= 100).

Process to the end of file.


Output

Write to the output file one non-negative number S - maximal possible area of the working region (in square meters). S must be written with two digits after the decimal point. If it is not possible to construct the fence from the specified blocks, write 0.00.


Sample Input

4
10
5
5
4
3
8
5
5
3
10
5
4
--
Could someone give some hints? Thx

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Fri May 14, 2004 4:41 pm

Using maths you can prove that for the maximum area, the points of the poligon with the given lengths must be on a circle. Now what you have to do is find the radius length using binary serach.

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Sat May 15, 2004 4:02 am

That problem is from Nothern European Regional, Nothern Subregion 2001. Take a look look at this http://neerc.ifmo.ru/subregions/northern.html

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Sat May 15, 2004 4:04 am

That problem is from Nothern European Regional, Nothern Subregion 2001. Take a look look at this http://neerc.ifmo.ru/subregions/northern.html

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Sat May 15, 2004 9:12 am

Cosmin.ro wrote:Using maths you can prove that for the maximum area, the points of the poligon with the given lengths must be on a circle. Now what you have to do is find the radius length using binary serach.
Yes, but how to binary search.
I have saw the official source code, but can't imagine why to do this?
Could you give more description?

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Sat May 15, 2004 9:18 am

For a radius R you can compute the size of the angle formed by the center O of the circle and the endpointa AB of a segment with length L, where A, B are on the circle. Summing sizes of angles up, if your result is bigger than 2pi the radius R must be bigger, else the radius must be smaller.

Post Reply

Return to “Algorithms”