VM 09 Bài 11 - Maximum area

View as PDF

Submit solution

Points: 1.21 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon 2009Round 5Problem Setter: Lê Ðôn Khuê
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một đa giác lồi ~N~ đỉnh. Các đỉnh được đánh số từ ~1~ đến ~N~. Hãy chọn ra ~K~ trong số ~N~ điểm tạo thành đa giác có diện tích lớn nhất có thể.

Input

  • Dòng đầu tiên ghi số ~N~ và ~K \;(3 \leq K \leq N \leq 200)~.
  • Dòng thứ ~U~ trong ~N~ dòng tiếp theo ghi hai số nguyên ~X_{u}~ và ~Y_{u}~ là tọa độ của điểm thứ ~U~. Các đỉnh được liệt kê theo chiều kim đồng hồ. Tọa độ các điểm có trị tuyệt đối nhỏ hơn hoặc bằng ~10^{5}~ .

Output

  • Dòng đầu tiên in ra diện tích của đa giác ~K~ đỉnh lớn nhất (làm tròn đến ~2~ chữ số thập phân).
  • Dòng thứ hai là dãy tăng gồm ~K~ số là số hiệu của các điểm được chọn.

Sample Input

4 3
1 2
3 1
2 0
1 1

Sample Output

1.50
1 2 3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.