Codeforces Round 743 (Div. 1) |
---|
Закончено |
У вас есть строго выпуклый многоугольник с $$$n$$$ вершинами.
Вы сделаете $$$k$$$ разрезов, удовлетворяющих следующим условиям:
Ваша задача — максимизировать площадь минимальной по площади области, образованной многоугольником и этими $$$k$$$ разрезами.
Первая строка содержит два целых числа $$$n$$$, $$$k$$$ ($$$3 \le n \le 200$$$, $$$0 \le k \le n-3$$$).
Следующие $$$n$$$ строк описывают вершины многоугольника в порядке против часовой стрелки. $$$i$$$-из этих строк содержит два целых числа $$$x_i$$$, $$$y_i$$$ ($$$|x_i|, |y_i| \le 10^8$$$) — координаты $$$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
В примере оптимально провести разрезы между следующими парами вершин:
Во втором примере оптимально провести разрезы между следующими парами вершин:
Название |
---|