Problem $4$

Given are n real numbers a$1,$ a$2,...,$ an$.$ Find a value t that can be obtained by adding two

of these numbers and, moreover, the number of pairs of these numbers that add up to t is the

largest possible. Formally, find a t such that the size of the set $\{($i$,$ j$)|$ i $<$ j$,$ ai $+$ aj $=$ t$\}$ is

maximum among all possible t$$s$.$ For example, for $2,7,3,1,5,6,$ we have: $2+6=7+1=3+5.$

This is the largest number of pairs that sum to the same number, and, therefore, t $=8.$ If

there are multiple possible t$$s$,$ find the smallest one. Give an O$($n

$2$

log n$)$ algorithm for this

problem.

Problem $4$

Input specification: The input consists of two lines. The first line contains a positive integer n$.$ The second line contains real numbers a$1,$ a$2,...,$ an$,$ separated by spaces. You may assume that the real numbers fit in double. You may also assume that n is at least $2$ and not larger than $10,000.$

Output specification: The output contains a single line with two numbers: the first is the largest number of pairs that sums to the same number, and the second is the number t $($i$.$e$.,$ the smallest sum with the largest number of corresponding pairs$).$ Output t with precision of six digits after the decimal point.

Sample input: input$-2\mathrm{.}1,$ input$-2\mathrm{.}2,$ input$-2\mathrm{.}3,$ input$-2\mathrm{.}4,$ input$-2\mathrm{.}5,$ input$-2\mathrm{.}6,$ input$-2\mathrm{.}8,$ input$-2\mathrm{.}9$

Sample output: answer$-2\mathrm{.}1,$ answer$-2\mathrm{.}2,$ answer$-2\mathrm{.}3,$ answer$-2\mathrm{.}4,$ answer$-2\mathrm{.}5,$ answer$-2\mathrm{.}6,$ answer$-2\mathrm{.}8,$ answer$-2\mathrm{.}9$

How to submit: Name your files FindMaxPairsDouble.java or FindMaxPairsDouble.cpp