Помогите, пожалуйста, с задачей по олимпиадному программированию!

Самое большое графство будет там, где разница между соседними границами максимальна. Перемножить горизонтальную на вертикальную разницы.
А вот как быстро и эффективно найти к-тое по размеру графство - это, может, дядя Андрей расскажет... Прямой перебор потенциального триллиона комбинаций выглядит страшновато. Скорее всего, надо отсортировать разницы границ по убыванию и как-то аккуратно идти по ним вниз, сравнивая получаемые площади, пока не найдется к-тая площадь.

Превращаешь координаты в длины отрезков: например первый отрезок по горизонтали будет равен y1, второй y2-y1 и т.д. - получится два списка X и Y (по вертикали и горизонтали соответственно)
Сортируешь оба списка (по убыванию). Затем нужно аккуратно реализовать следующую логику:
Во-первых, самой большой площадью будет Y[0]*X[0] (если какой-то из списков пустой - то взять w или h соответственно)
Затем найдем минимальную площадь:
Пусть i = 0, j = 0, total=0

1. Пусть X[i]>Y[j] (если наоборот, то все дальнейшие шаги сделать зеркально - поменять i на j, X на Y и т.п.)
2. Бинарным поиском ищем наибольшее u такое что X[i]*Y[u] >= X[i+1]*Y[j]
3. total+=u-j+1
4. Прекратить если total >= k
5. i++
6. Повторить с пункта 1

Минимальная площадь=max(X[i]*Y[j+total-k], X[i+total-k]*Y[j])


Сложность O(n*log(m)+m*log(n)) ну то есть по фигне. И памяти только на хранение двух списков на 10^5