eolymp
bolt
Try our new interface for solving problems
Məsələlər

Хоккей

Хоккей

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

После провального выступления в Ванкувере сборной России по хоккею только ленивый не обсуждал это и не пытался озвучить свою версию происшедшего. Одни обвиняли игроков сборной России в нежелании бороться, другие восхищались бешеным настроем канадцев на игру. Руководители российского хоккея также предположили, что немалую роль в поражении сыграли канадские площадки, размеры которых значительно отличаются от привычных нам европейских. Для того чтобы на следующей олимпиаде в Сочи взять реванш за поражение, было решено удивить канадцев «русскими» площадками.

Русская площадка для игры в хоккей представляет собой выпуклый многоугольник. Уж на таком-то катке русские обязательно одолебт и канадцев, и всех остальных. Однако строители столкнулись с проблемой разметки такой площадки. Первым делом было решено провести центральную линию. Строители рассудили, что центральная линия должна проходить через некоторые две вершины многоугольника и при этом так делить площадку на два «полумногоугольника», чтобы отношение площади меньшего «полумногоугольника» к площади большего было максимально близко к 1 или равно 1.

Необходимо помочь строителям найти центральную линию.

Giriş verilənləri

В первой строке записано целое число T – количество тестовых блоков (1T10). Далее записано T тестовых блоков. Каждый тестовый блок содержит число N - количество вершин многоугольника (4N2000), и далее N строк по два целых числа – координаты вершин многоугольника. Координаты не превосходят 10000 по своему абсолютному значению.

Çıxış verilənləri

Для каждого тестового блока необходимо вывести по две строки. В первой строке вывести два числа – номера вершин, через которые проводится разделяющая диагональ. Номера должны быть упорядочены по возрастанию. Нумерация начинается с 1 и соответствует порядку вершин во входных данных. Во второй строке вывести правильную несократимую дробь – отношение площадей. Если возможно несколько правильных решений, вывести решение с наименьшим номером первой вершины. Если и в этом случае возможно несколько правильных решений, вывести решение с наименьшим номером второй вершины.

Nümunə

Giriş verilənləri #1
1
5
0 0
-1 3
2 7
5 4
5 1
Çıxış verilənləri #1
2 4
21/34
Müəllif Бирюков С.В.
Mənbə IV Открытая олимпиада ЮФУ