Задача №113321. Парадокс с дробями
Никита очень любит математические парадоксы. Недавно он заметил, что
\(\)\frac{2}{3} < \frac{1}{1}; \frac{1}{2} < \frac{6}{11},\(\) но при этом если у меньших дробей сложить числители и знаменатели и то же сделать с большими дробями, то получатся дроби
\(\)\frac{2+1}{3+2} = \frac{3}{5}; \frac{1+6}{1+11} = \frac{7}{12},\(\) причем \(\)\frac{3}{5} > \frac{7}{12}.\(\) Тогда Никита выписал в ряд \(k\) дробей и хочет выбрать среди них четыре дроби, чтобы выполнялись неравенства \(\)\frac{m_1}{n_1} \le \frac{m_2}{n_2}; \frac{m_3}{n_3} \le \frac{m_4}{n_4},\(\) а величина \(\)\frac{m_1 + m_3}{n_1 + n_3} - \frac{m_2 + m_4}{n_2 + n_4}\(\) была максимальна. Каждую из записанных дробей можно взять только в качестве одной из выбранных четырех. Помогите Никите решить эту сложную задачу.
Первая строка ввода содержит число \(k\) — количество дробей, выписанных Никитой (\(4 \le k \le 2000\)).
Следующие \(k\) строк содержат по два положительных целых числа: для каждой дроби задан ее числитель и знаменатель. Все заданные дроби являются несократимыми. Числитель и знаменатель каждой дроби не превышают 10 000.
Выведите четыре различных целых числа: номера дробей, которые следует выбрать в качестве \(\frac{m_1}{n_1}, \frac{m_2}{n_2}, \frac{m_3}{n_3}, \frac{m_4}{n_4}\), соответственно. Дроби пронумерованы от \(1\) до \(n\) в том порядке, в котором они заданы во вводе. Если возможных оптимальных решений несколько, разрешается выдать любое из них.