Giải bài trực tuyến

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ể.

Dữ liệu

• Dòng đầu tiên ghi số N và K (3 ≤ K ≤ N ≤ 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⁵.

Kết quả

• 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.

Ví dụ

Dữ liệu
4 3
1 2
3 1
2 0
1 1

Kết quả
1.50
1 2 3