Отборочный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"D" Остроугольные треугольники
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Совсем недавно московский десятиклассник Дмитрий Захаров обогнал всех в построении множества точек в d-мерном пространстве, таких что все треугольники с вершинами в этих точках остроугольные.

Таня решила померяться силами с Дмитрием. Разумеется, она планирует использовать компьютер. Для начала она хочет решить следующую задачу. Дано n точек на плоскости, требуется найти количество остроугольных треугольников с вершинами в этих точках. Треугольник называется остроугольным, если все его углы строго меньше 90 градусов.

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 666).

Каждый из тестов описывается следующим образом: в первой строке описания теста содержатся число n (3 ≤ n ≤ 2000) — количество точек.

В следующих n строках содержатся по два числа xi, yi ( - 109 ≤ x, y ≤ 109) — координаты точек. Гарантируется, что все точки в одном тесте различные.

Суммарное количество точек по всем тестам одних входных данных не превосходит 2000.

Формат выходных данных

Для каждого теста в отдельной строке выведите ответ на него — количество остроугольных треугольников с вершинами в заданных точках.

Примеры
Входные данные
2
5
1 1
2 2
3 3
4 1
6 4
5
0 0
3 1
5 1
5 -1
1 3
Выходные данные
3
4
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.