1263 . 保加利亞的多邊形

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

minson123

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

30.4% (7/23)

Tags

BULOI 2008-BULOI-fin

Description

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

Input Format

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

Output Format

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

Sample Input 1

4 3
0 0
1 1
0 10
10 0

Sample Output 1

5

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10
10 10000 65536 262144 11
Submit
Back to Top