Задача C. Суммарная площадь
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Альтаиру часто дарят интересные подарки. На этот раз Ариф подарил множество различных
точек на плоскости, он конечно поблагодарил Арифа. Но он совсем не знает что делать с этими
точками, поэтому он придумал задачу.
Альтаир определил функцию f(S), которая считает площадь минимального прямоугольника со
сторонами параллельными осям координат, который покрывает все точки из множества S (точка
покрыта прямоугольником, когда находится внутри него или на его границе). Но подсчет такой
функции кажется ему чем-то слишком простым и скучным, поэтому он хочет посчитать сумму
значений функции f по всем возможным непустым подмножествам точек.
Так как Альтаир не умеет использовать большие числа, а ответ может быть уж слишком большим, поэтому нужно посчитать его остаток при делении на 109 + 7.
Формат входных данных
В первой строке дано одно натуральное число n (1 6 n 6 105
) — количество точек в подарке.
Далее следуют n строк, в i-й записана пара чисел xi
, yi (1 6 xi
, yi 6 109
) — координаты i-й
точки.
Формат выходных данных
Выведите одно число - ответ на задачу по модулю 109 + 7.
Система оценки
Подзадача Дополнительные ограничения Баллы Необходимые подзадачи
0 Примеры 0 —
1 n = 2 9
2 n 6 20 11 1
3 n 6 200 15 1, 2
4 n 6 2 000 25 1, 2, 3
5 n 6 100 000 40 1, 2, 3, 4
Пример
стандартный ввод стандартный вывод
3
4 10
5 7
7 9
19
Замечание
Рассмотрим пример. В этом примере есть 7 непустых подмножеств.
Площадь прямоугольника для подножества из первой и второй точки: f({1, 2}) = 3.
f({1}) = f({2}) = f({3}) = 0
f({1, 2}) = 3
f({1, 3}) = 3
f({2, 3}) = 4
f({1, 2, 3}) = 9
Сумма по всем f(S) – 19.
Ответы
# ruby v3.2
def parse_input
n = gets().to_i
points = []
n.times {
points << gets().strip().split(" ").map{|i| i.to_i}
}
return points
end
def rectangle_square(points)
# длина прямоугольника = разница максимального и минимального Х
wwidth = points.max_by{|point| point[0]}[0] - points.min_by{|point| point[0]}[0]
# высота прямоугольника = разница максимального и минимального У
hheight = points.max_by{|point| point[1]}[1] - points.min_by{|point| point[1]}[1]
return wwidth * hheight
end
def zadacha1(points)
p points
require 'enumerator'
s = 0
(1..points.size).each { |i|
# находим все возможные сочетания из i точек (хорошо что в руби есть встроенная функция для этого)
points.combination(i) { |combination|
# p combination
s += rectangle_square(combination)
}
}
return s
end
p zadacha1([[4, 10], [5, 7], [7, 9], ]) #тестовые данные
p zadacha1(parse_input) #ввод с консоли