Звёзды над Сары-Челеком


Отправить решение Решать в редакторе

Сложность: 80%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Астроном Эрмек снимает звёздное небо над озером Сары-Челек. На снимке 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.


Комментарии

Еще нет ни одного комментария.