Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Упаковка

Первоисточник: Цикл Интернет-олимпиад для школьников

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

Сдать задачу

Задать вопрос жюри по этой задаче