Упаковка
Первоисточник: Цикл Интернет-олимпиад для школьников
URL первоисточника: http://ctddev.ifmo.ru/school/io/archive.html
Задачу добавил: elena
Успешно сдано решений: 10
Упаковка
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Вот уже неделю Ваня решает сложную задачу: по данному числу n необходимо расположить на плоскости n кругов с радиусами 1, 2, ..., n таким образом, чтобы, во-первых, каждая пара кругов не пересекалась (возможно, касаясь), а во-вторых, все эти круги помещались в большой объемлющий
круг как можно меньшего радиуса. В процессе решения Ваня заметил, что, расположив достаточное количество больших кругов, можно сразу начинать искать объемлющий круг, поскольку все оставшиеся маленькие круги можно поместить в промежутках, оставшихся между большими. Теперь Ваня хочет по данному множеству радиусов оценить, как часто между тремя попарно
касающимися кругами с радиусами из этого множества можно поместить четвертый круг. Для этого он ввел рейтинг упаковываемости P: для множества радиусов R = {r1, r2, ..., rn} рейтинг P(R) равен количеству таких упорядоченных четверок индексов (i, j, k, l), что ri > rj > rk > rl и между
тремя попарно касающимися кругами радиусов ri, rj и rk можно поместить круг радиуса rl так, чтобы он не пересекался с ними, возможно, касаясь. Выражение "поместить между" означает, что центр четвертого круга должен лежать внутри треугольника с вершинами в центрах первых трех кругов.
Помогите Ване посчитать рейтинг упаковываемости данного множества.
Формат входного файла
В первой строке входного файла записано целое число n (1<= n<= 250). Во второй строке через пробел записаны n различных целых чисел r1, r2, ..., rn (1<= ri<= 250) - элементы множества R.
Гарантируется, что R непусто.
Формат выходного файла
Выведите в выходной файл одно число - рейтинг упаковываемости P(R).
Пример входного файла
5
2 1 5 10 20
Пример выходного файла
1