Арена Скайболу#746
Федерація магічних видів спорту вирішила створити нову гру з літаючим м'ячем під назвою Скайбол, натхненну традиційними видами спорту на мітлах. На відміну від звичайного овального поля, новатори запропонували використовувати арену у формі опуклого многокутника, що ширяє в повітрі. Така незвична форма зробить гру більш динамічною і непередбачуваною.
Однак будівельники арени зіткнулись з проблемою. Згідно з правилами гри, арена повинна бути розділена центральною лінією на дві зони, і ці зони мають бути максимально рівними за площею для забезпечення чесної гри. Центральна лінія повинна проходити через дві вершини многокутника і ділити арену на дві частини так, щоб відношення площі меншої частини до площі більшої було максимально близьким до або рівним .
Допоможіть будівельникам знайти оптимальну центральну лінію.
У першому рядку записано ціле число – кількість тестових блоків (1 \leq T \leq 10). Далі записано тестових блоків. Кожен тестовий блок містить число - кількість вершин многокутника (4 \leq N \leq 2000), і далі рядків по два цілих числа – координати вершин многокутника. Координати не перевищують по своєму абсолютному значенню.
Для кожного тестового блоку необхідно вивести по два рядки. У першому рядку вивести два числа – номери вершин, через які проводиться розділяюча діагональ, у зростаючому порядку. Нумерація починається з і відповідає порядку вершин у вхідних даних. У другому рядку вивести правильний нескоротний дріб – відношення площ. Якщо можливо декілька правильних розв'язків, вивести розв'язок з найменшим номером першої вершини. Якщо і у цьому випадку можливо декілька правильних розв'язків, вивести розв'язок з найменшим номером другої вершини.
Приклад 1