Задача Trees2018. Робот-провідник моделі TouristVasya призначений для організації туристичних походів лісами Поділля. Нещодавно у ньому знайшли проблему - у деяких ситуаціях робот може заблукати в чотирьох соснах. Працівники туристичної компанії, яка купила робота, вже зрозуміли алгоритм, за яким робот обходить перешкоди: натикаючись на дерево, робот повертає на 90 градусів праворуч, після чого йде прямолінійно до наступної зустрічі з деревом (або поки не вийде з лісу). На жаль, виправлення помилок програмного забезпечення - справа довготривала i дорога, тож туристична компанія вирішила знайти усі проблемні маршрути i видати відповідні брошури з рекомендаціями туристам. Проблемним маршрутом назвемо замкнену послідовність обходу роботом чотирьох дерев, при цьому робот жодним чином (рухаючись за алгоритмом) вийти з цього маршруту не може. Вам доручається розробити програму, яка б за мапою дерев визначила б кількість проблемних маршрутів. Маршрути вважаються різними, якщо відрізняється четвірка дерев, що входить у цей маршрут. До прикладу, четвірки (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,
|
