Problem Description

Meow Meow is a very rich cat. He owns a large garden in Haidian District.

This garden is an $N$-gon (a polygon with $N$ sides) formed by some old fences as its boundary.

Since Christmas is coming soon, Meow Meow wants to decorate the garden with $K$ Christmas trees. At the same time, he firmly believes that finding some good places to plant trees will bring him good luck.

As a good cat, he decides to find the best positions as follows:

• All trees should be on the boundary of the garden.
• The $K$ trees should evenly divide the perimeter of the garden.
• The area of the new convex $K$-gon formed by the trees should be as small as possible.

Although Meow Meow is richer than you, he is not as smart as you. Therefore, he gives you some money and asks you to help him find the minimum area of the convex $K$-gon.

Input Format

The first line contains two integers, $N$ and $K$, representing the number of vertices of the original garden boundary and the number of trees.

Each of the next $N$ lines contains two integers $x_i$ and $y_i$, describing the coordinates of a vertex of the garden boundary.

All coordinates are given in counterclockwise order.

Output Format

Output the minimum area of the convex $K$-gon. Your answer will be considered correct if the relative or absolute error does not exceed $10^{-8}$.

5 4
0 0
1 0
2 1
2 2
0 2

1.9892766953

3 3
0 0
1 0
0 1

0.1226170434

Hint

Constraints

• $3 \le N, K \le 1000$.
• $-10^5 \le x_i, y_i \le 10^5$.

Translated by ChatGPT 5