SMAX - Maximum area

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 Xu và Yu 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 105.

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


Được gửi lên bởi:Lê Đôn Khuê
Ngày:2009-07-31
Thời gian chạy:0.200s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ADA95 ASM32 BASH BF C CSHARP C99 CLPS LISP clisp LISP sbcl D ERL FORTRAN GOSU HASK ICON ICK JS-RHINO LUA NEM NICE OCAML PAS-GPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYPY RUBY RUST SCM guile SCM qobi SED ST WHITESPACE
Nguồn bài:VNOI Marathon 2009
Round 5
Problem Setter: Lê Đôn Khuê

hide comments
2017-06-05 19:01:57
bài này làm kiểu gì vậy mấy anh
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.