Задача №114848. Парадокс с дробями
Никита очень любит математические парадоксы. Недавно он заметил, что 2 / 3 ≤ 1 / 1;1 / 2 ≤ 6 / 11 но при этом если у меньших дробей сложить числители и знаменатели и то же сделать с большими дробями, то получатся дроби (2 + 1) / (3 + 2) = 3 / 5 и (1 + 6) / (1 + 11) = 7 / 12, причем 3 / 5 ≥ 7 / 12.
Тогда Никита выписал в ряд
k
дробей и хочет выбрать среди них четыре дроби, чтобы выполнялись неравенства
а величина
(
m
1
+
m
3
) / (
n
1
+
n
3
) - (
m
2
+
m
4
) / (
n
2
+
n
4
)
была максимальна. Каждую из записанных дробей можно взять только в качестве одной из выбранных четырех. Помогите Никите решить эту сложную задачу.
Первая строка ввода содержит число k — количество дробей, выписанных Никитой ( 4 ≤ k ≤ 2000 ).
Следующие k строк содержат по два положительных целых числа: для каждой дроби задан ее числитель и знаменатель. Все заданные дроби являются несократимыми. Числитель и знаменатель каждой дроби не превышают 10 000 .
Выведите четыре различных целых числа: номера дробей, которые следует выбрать в качестве m 1 / n 1 , m 2 / n 2 , m 3 / n 3 и m 4 / n 4 , соответственно. Дроби пронумерованы от 1 до n в том порядке, в котором они заданы во вводе. Если возможных оптимальных решений несколько, разрешается выдать любое из них.
4 1 1 1 2 2 3 6 11
2 4 3 1