TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

23.5% (4/17)

Description

保加利亞的多邊形是很特別的,它們都是凸多邊形,而且都恰好有$K$個邊。給定平面上的 $N$ 個相異位置的點,而且不會有三個點共線的情形。
請找出以其中$K$個頂點所圍成的保加利亞多邊形之最小面積。

Input Format

第一列有兩個整數 $N, K$, $(0 < N < 50, 0 < K< 11)$。
接下來有$N$列每列有兩個整數描述一個點的座標。所有點的座標值都是非負整數,並且不超過$9999$。

Output Format

你的程式應該輸出凸$K$邊形的最小面積的整數部分,如果找不到這樣的多邊形,請輸出 $0$。

Sample Input

4 3
0 0
1 1
0 10
10 0

Sample Output

5

Hints

Problem Source

原TIOJ1263 / Bulgarian National Olympiad in Informatics 2008 Final (Prob A2)

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 10000 65536
1 10000 65536
2 10000 65536
3 10000 65536
4 10000 65536
5 10000 65536
6 10000 65536
7 10000 65536
8 10000 65536
9 10000 65536
10 10000 65536