Звёзды над Сары-Челеком
Астроном Эрмек снимает звёздное небо над озером Сары-Челек. На снимке n звёзд, звезда i имеет целые координаты (x[i], y[i]), а в начале координат (0, 0) — Полярная звезда (её саму в список не включили). Никакие две звезды не лежат на одной прямой с Полярной звездой.
Эрмек выбирает три звезды и соединяет их в треугольник. Сколько существует треугольников, внутри которых оказывается Полярная звезда?
Входные данные
В первой строке — число n (3 ≤ n ≤ 2 · 10⁵). В каждой из следующих n строк — два целых числа x[i] y[i] (|x[i]|, |y[i]| ≤ 10⁹, звезда не в начале координат).
Выходные данные
Выведите количество треугольников, строго внутри которых лежит точка (0, 0).
Пример 1
Вход:
4
2 1
-1 2
-2 -3
3 -3
Выход:
2
Пояснение
Из четырёх треугольников, которые можно составить из звёзд примера, начало координат содержат два.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 100, ещё в 5 % тестов n ≤ 2000.
Комментарии