Задача Trees2018. Робот-проводник модели TouristVasya предназначен для организации туристических походов лесами Подолья. Недавно в нем нашли проблему - в некоторых ситуациях робот может заблудиться в четырех соснах. Работники туристической компании, которая купила робота, уже поняли алгоритм, по которому робот обходит препятствия: натыкаясь на дерево, робот поворачивает на 90 градусов направо, после чего идет прямолинейно к следующей встрече с деревом (или пока не выйдет из леса). К сожалению, исправление ошибок программного обеспечения - дело долговременное и дорогое, поэтому туристическая компания решила найти все проблемные маршруты и выдать соответствующие брошюры с рекомендациями туристам. Проблемным маршрутом назовем замкнутую последовательность обхода роботом четырех деревьев, при этом робот никоим образом (двигаясь по алгоритму) выйти из этого маршрута не может. Вам поручается разработать программу, которая бы по карте деревьев определила бы количество проблемных маршрутов. Маршруты считаются разными, если отличается четверка деревьев, входящих в этот маршрут. Например, четверки (1,2,3,4) и (3,2,1,4) одинаковые, в то время как (1,2,3,5) и (1,5,4,3) - разные.
Технические условия. Программа Trees2018 читает с устройства стандартного введения в первой строке целое число N(1≤N≤1000) - количество деревьев на карте. В следующих N строках координаты деревьев в формате xiyi. При этом каждая из координат не превышает 109 по абсолютной величине. Никаких два дерева не размещены в одной точке. Никаких три дерева не размещены на одной прямой. Программа выводит на устройство стандартного вывода единственное число - количество проблемных маршрутов.
Примеры
|
Ввод
|
Вывод
|
Ввод
|
Вывод
|
|
8
1 0
0 1
-1 0
0 -1
2 2
2 4
4 2
4 4
|
2
|
8
1 2
2 1
-1 2
-2 1
1 -2
2 -1
-1 -2
-2 -1
|
6
|
Пояснения к примерам:
Проблемные маршруты такие:
- 3 → 2 → 1 → 4 → 3,
- 5 → 6 → 8 → 7 → 5,
Проблемные маршруты такие:
- 3 → 1 → 5 → 7 → 3,
- 3 → 2 → 5 → 8 → 3,
|
