Задача №111557. Страусиные страсти
Как вы помните, у Джонни приключился досадный инцидент со страусом Чаком. Поймав всех разбежавшихся страусов, фермер задумался о том, как бы не повторить подобного беспорядка в будущем.
Джонни принял решение построить новое жильё для птиц. Он поставил N наблюдательных вышек с часовыми и прожекторами и соединил их заборами с колючей проволкой под напряжением, огородив тем самым дворик в форме многогуольника из N вершин, на котором будут жить страусы. Для простоты наблюдения он хочет соединить некоторые пары несоседних вышек стенами с пулемётчиками, разбив тем самым двор на N - 2 треугольных части, образующих загоны для страусов. Естественно, стены должны лежать целиком внутри многоугольника, и каждый загон должен представлять собой невырожденный треугольник, т. е. его площадь должна быть ненулевой.
Сейчас фермеру предстоит выбрать, как именно он будет разбивать двор. Помогите ему проанализировать все возможные варианты проведения стен. Джонни интересуют два вопроса — как водится, попроще и посложнее. Во-первых, он хочет знать, для каких пар вышек существует план разбиения, включающий стену между ними. Во-вторых, его интересует, сколько вообще существует планов разбиения двора.
В первой строке входного файла идёт число N (3 ≤ N ≤ 300) — количество вышек.
В последующих N строках даны описания вышек по порядку их обхода. i-я строка содержит два целых числа xi, yi, по модулю не превосходящих 104 — координаты i-ой вышки.
Гарантируется, что двор представляет собой многоугольник ненулевой площади без самокасаний и самопересечений.
В первой строке выведите K — количество пар вышек, между которым потенциально может быть проведена стена.
Далее выведите K пар номеров вышек по одному в каждой строке. Числа в каждой паре должны быть упорядочены по возрастанию, пары должны идти сначала по возрастанию первых чисел, потом по возрастанию вторых чисел.
Последняя строка должна содержать единственное число — количество способов поделить двор на загоны. Так как оно может быть достаточно большим, выведите остаток от его деления на 230 = 1073741824.
Тесты к этой задаче состоят из четырех групп.
- Тесты 1-2. Тесты из условия, оцениваются в ноль баллов.
- Тесты 3-18. В тестах этой группы N не превосходит 12. Группа оценивается в 20 баллов.
- Тесты 19-26. В тестах этой группы двор представляет строго выпуклый многоугольник. Группа оценивается в 20 баллов.
- Тесты 27-42. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 60 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из второй и третьей групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
5 1 1 3 3 4 0 2 -2 1 0
5 1 3 1 4 2 4 2 5 3 5 5
6 2 2 1 4 0 2 2 0 4 2 3 4
5 1 3 1 4 1 5 2 4 4 6 4