Codeforces Round 743 (Div. 1) |
---|
Закончено |
У вас есть строго выпуклый многоугольник с n вершинами.
Вы сделаете k разрезов, удовлетворяющих следующим условиям:
Ваша задача — максимизировать площадь минимальной по площади области, образованной многоугольником и этими k разрезами.
Первая строка содержит два целых числа n, k (3≤n≤200, 0≤k≤n−3).
Следующие n строк описывают вершины многоугольника в порядке против часовой стрелки. i-из этих строк содержит два целых числа xi, yi (|xi|,|yi|≤108) — координаты i-й вершины.
Гарантируется, что многоугольник выпуклый и никакие две смежные стороны не параллельны.
Выведите одно целое число: максимально возможную площадь самой маленькой области после k разрезов, умноженную на 2.
8 4 -2 -4 2 -2 4 2 1 5 0 5 -4 4 -5 0 -5 -1
11
6 3 2 -2 2 -1 1 2 0 2 -2 1 -1 0
3
В примере оптимально провести разрезы между следующими парами вершин:
Во втором примере оптимально провести разрезы между следующими парами вершин:
Название |
---|