Задачи
Хоккей
Хоккей
\includegraphics{https://static.e-olymp.com/content/0a/0a25237785ffa07b2842fb4280656cc65b0d7341.jpg}
После провального выступления в Ванкувере сборной России по хоккею только ленивый не обсуждал это и не пытался озвучить свою версию происшедшего. Одни обвиняли игроков сборной России в нежелании бороться, другие восхищались бешеным настроем канадцев на игру. Руководители российского хоккея также предположили, что немалую роль в поражении сыграли канадские площадки, размеры которых значительно отличаются от привычных нам европейских. Для того чтобы на следующей олимпиаде в Сочи взять реванш за поражение, было решено удивить канадцев <<русскими>> площадками.
Русская площадка для игры в хоккей представляет собой выпуклый многоугольник. Уж на таком-то катке русские обязательно одолебт и канадцев, и всех остальных. Однако строители столкнулись с проблемой разметки такой площадки. Первым делом было решено провести центральную линию. Строители рассудили, что центральная линия должна проходить через некоторые две вершины многоугольника и при этом так делить площадку на два <<полумногоугольника>>, чтобы отношение площади меньшего <<полумногоугольника>> к площади большего было максимально близко к \textbf{1} или равно \textbf{1}.
Необходимо помочь строителям найти центральную линию.
\InputFile
В первой строке записано целое число \textbf{T} -- количество тестовых блоков (\textbf{1} ≤ \textbf{T} ≤ \textbf{10}). Далее записано \textbf{T} тестовых блоков. Каждый тестовый блок содержит число \textbf{N} - количество вершин многоугольника (\textbf{4} ≤ \textbf{N} ≤ \textbf{2000}), и далее \textbf{N} строк по два целых числа -- координаты вершин многоугольника. Координаты не превосходят \textbf{10000} по своему абсолютному значению.
\OutputFile
Для каждого тестового блока необходимо вывести по две строки. В первой строке вывести два числа -- номера вершин, через которые проводится разделяющая диагональ. Номера должны быть упорядочены по возрастанию. Нумерация начинается с \textbf{1} и соответствует порядку вершин во входных данных. Во второй строке вывести правильную несократимую дробь -- отношение площадей. Если возможно несколько правильных решений, вывести решение с наименьшим номером первой вершины. Если и в этом случае возможно несколько правильных решений, вывести решение с наименьшим номером второй вершины.
Входные данные #1
1 5 0 0 -1 3 2 7 5 4 5 1
Выходные данные #1
2 4 21/34