Задача 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,