13869번 - Dating On-Line 다국어

Alex registered in an online dating system to search for the perfect partner. The system requires each of its members to fill a form specifying how much they enjoy N different activities, grading them on a scale from 0 to 100. To present this information to potential dates, the system creates a profile featuring a special kind of polygon called “radial diagram”.

A radial diagram for N activities is drawn by marking N points on the plane. Starting from the vertical direction, the i-th point in clockwise order represents the i-th activity specified by the member, and is a distance S_i away from the center of the diagram, where S_i is the score given by the member for the corresponding activity. The angle sustained at the center of the diagram from each pair of consecutive points is always the same, and the polygon is formed by drawing the segments whose endpoints are consecutive points. Note that for the purposes of the radial diagram, the first and last points are considered to be consecutive.

For example, if N = 6 Alex might specify the following activities: singing with score S₁ = 10, running with score S₂ = 60, listening to music with score S₃ = 70, traveling with score S₄ = 70, eating out with score S₅ = 80, and visiting museums with score S6 = 80. Then the corresponding radial diagram would be as shown in the figure below.

The area of a radial diagram depends on the order in which the different activities are specified, and Alex suspects that a profile depicting a radial diagram with greater area might be more successful. For example, the radial diagram in the following figure features the same activities and scores as the example above, but has a greater area.

Alex has asked you to write a program to find the maximum possible area of a radial diagram given a list of activities graded with scores between 0 and 100.

The first line contains an integer N representing the number of activities (3 ≤ N ≤ 10⁵ ). The second line contains N integers S₁, S₂, . . . , S_N representing the scores given by Alex to each activity (0 ≤ S_i ≤ 100 for i = 1, 2, . . . , N)

Output a line with a rational number representing the maximum possible area of a radial diagram featuring the scores given in the input. The result must be output as a rational number with exactly 3 digits after the decimal point, rounded if necessary.