Submit solution
Points:
1.21 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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