Страусиные страсти
Как вы помните, у Джонни приключился досадный инцидент со страусом Чаком. Поймав всех разбежавшихся страусов, фермер задумался о том, как бы не повторить подобного беспорядка в будущем.
Джонни принял решение построить новое жильё для птиц. Он поставил N наблюдательных вышек с часовыми и прожекторами и соединил их заборами с колючей проволокой под напряжением, огородив тем самым дворик в форме многоугольника из N вершин, на котором будут жить страусы. Для простоты наблюдения он хочет соединить некоторые пары не соседних вышек стенами с пулемётчиками, разбив тем самым двор на N-2 треугольных части, образующих загоны для страусов. Естественно, стены должны лежать целиком внутри многоугольника, и каждый загон должен представлять собой невырожденный треугольник, т. е. его площадь должна быть ненулевой.
Сейчас фермеру предстоит выбрать, как именно он будет разбивать двор. Помогите ему проанализировать все возможные варианты проведения стен. Джонни интересуют два вопроса — как водится, попроще и посложнее. Во-первых, он хочет знать, для каких пар вышек существует план разбиения, включающий стену между ними. Во-вторых, его интересует, сколько вообще существует планов разбиения двора.
Входные данные
В первой строке входного файла идёт число N (3 ≤ N ≤ 300) — количество вышек.
В последующих N строках даны описания вышек по порядку их обхода. i-я строка содержит два целых числа x_i, y_i, по модулю не превосходящих 10^4 — координаты i-ой вышки.
Гарантируется, что двор представляет собой многоугольник ненулевой площади без самокасаний и самопересечений.
Выходные данные
В первой строке выведите K — количество пар вышек, между которым потенциально может быть проведена стена.
Далее выведите K пар номеров вышек по одному в каждой строке. Числа в каждой паре должны быть упорядочены по возрастанию, пары должны идти сначала по возрастанию первых чисел, потом по возрастанию вторых чисел.
Последняя строка должна содержать единственное число — количество способов поделить двор на загоны. Так как оно может быть достаточно большим, выведите остаток от его деления на 2^30 = 1073741824.