Хоккей
После провального выступления в Ванкувере сборной России по хоккею только ленивый не обсуждал это и не пытался озвучить свою версию происшедшего. Одни обвиняли игроков сборной России в нежелании бороться, другие восхищались бешеным настроем канадцев на игру. Руководители российского хоккея также предположили, что немалую роль в поражении сыграли канадские площадки, размеры которых значительно отличаются от привычных нам европейских. Для того чтобы на следующей олимпиаде в Сочи взять реванш за поражение, было решено удивить канадцев «русскими» площадками.
Русская площадка для игры в хоккей представляет собой выпуклый многоугольник. Уж на таком-то катке русские обязательно одолебт и канадцев, и всех остальных. Однако строители столкнулись с проблемой разметки такой площадки. Первым делом было решено провести центральную линию. Строители рассудили, что центральная линия должна проходить через некоторые две вершины многоугольника и при этом так делить площадку на два «полумногоугольника», чтобы отношение площади меньшего «полумногоугольника» к площади большего было максимально близко к 1 или равно 1.
Необходимо помочь строителям найти центральную линию.
Входные данные
В первой строке записано целое число T – количество тестовых блоков (1 ≤ T ≤ 10). Далее записано T тестовых блоков. Каждый тестовый блок содержит число N - количество вершин многоугольника (4 ≤ N ≤ 2000), и далее N строк по два целых числа – координаты вершин многоугольника. Координаты не превосходят 10000 по своему абсолютному значению.
Выходные данные
Для каждого тестового блока необходимо вывести по две строки. В первой строке вывести два числа – номера вершин, через которые проводится разделяющая диагональ. Номера должны быть упорядочены по возрастанию. Нумерация начинается с 1 и соответствует порядку вершин во входных данных. Во второй строке вывести правильную несократимую дробь – отношение площадей. Если возможно несколько правильных решений, вывести решение с наименьшим номером первой вершины. Если и в этом случае возможно несколько правильных решений, вывести решение с наименьшим номером второй вершины.