003 - 有理式最大化

問題

N個の異なる自然数が与えられる。その中から異なる４つを選んで、それらをA, B, C, Dとしたとき、次の数式

の最大値を求めたい。上式のA, B, C, Dに、与えられた自然数のすべての組み合わせを代入して、最大値を変数maxvalに記録する方式の処理例を以下に示す。ただし、与えられた自然数はdata[0],data[1],..., data[N-1]に格納されている。

この処理は、個数Nが小さいときは直ちに終了するが、 Nが大きくなると結果を得るまでに時間がかかるようになるので望ましくない。なぜならば、ループの最も内側の計算は、N×(N−1)×(N−2)×(N−3)回繰り返されるためである。たとえば、Nが1000になると、この処理のループの最も内側の計算は約10¹²（１兆）回繰り返されることになり、計算の速いコンピュータでもすぐに答えを得ることはできない。ところが、上より効率の良い処理を行うプログラムを作成することにより、 Nが1000程度であっても短い時間で答えを得ることができる。

課題

N個の異なる自然数が与えられたとき、その中から異なる４つを選んで、上の数式の最大値を求めるプログラムを作成せよ。ただし、上の処理をそのまま利用したプログラムを提出すると、時間制限で誤答となることに注意せよ。

入力

N
a1 a2 ... aN

１行目に自然数の個数N(4≦N≦1000)が与えられる。２行目に各自然数の値a_i(1≦a_i≦10⁸)が与えられる。ただし、同じ自然数が重複して現れることはない（i≠jについてa_i≠a_j)。

時間制限

入力に対して、実行時間が２秒を超えてはならない。

出力

与えられたN個の自然数に対して、上の数式の最大値を実数で出力する。ただし、誤差がプラスマイナス10^-5 を超えてはならない。この条件を満たせば、小数点以下を何桁表示してもよい。

---

入出力例

入力例1

10
1 2 3 4 5 6 7 8 9 10

出力例1

19.00000

入力例１では、A=9, B=10, C=2, D=1などの組み合わせで最大になる。この場合は、小数点以下を省略して「19」と出力しても良い。

入力例2

5
22 100 42 3 86

出力例2

9.78947

入力例２では、A=100, B=86, C=22, D=3などの組み合わせで最大になる。

入力例3

6
15 21 36 10 34 5

出力例3

18.00000

入力例３では、A=21, B=15, C=36, D=34などの組み合わせで最大になる。

入力例4

4
100000 99999 8 1

出力例4

28571.285714

C++のiostreamのcoutを使う場合、coutを行う前に以下の関数を呼び出せば、小数点以下6桁までを出力させることができる。
std::cout.setf(std::ios_base::fixed,std::ios_base::floatfield);