| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P134SUMH - SUM4 H - Đa giác không tự cắt |
Cho n điểm trên mặt phẳng, trong đó có ít nhất 3 điểm không thẳng hàng. Từ các điểm trong n điểm trên ta có thể dựng được rất nhiều đa giác đa giác. Trong bài toán này sẽ quan tâm đến các đa giác không tự cắt và diện tích của chúng. Đa giác không tự cắt là đa giác không có cặp cạnh nào cắt nhau (không nhất thiết phải đa giác lồi).
Yêu cầu: Cho n điểm và số nguyên k, hãy tìm ít nhất ba điểm và không quá k điểm trong n điểm trên, sau đó dựng một đa giác không tự cắt từ các điểm được chọn để được đa giác có diện tích là lớn nhất.
Input
Dòng đầu gồm hai số nguyên dương n và k (3 <= k <= n <= 200).
n dòng tiếp theo, mỗi dòng gồm 2 số xi, yi (có giá trị tuyệt đối <= 106) là tọa độ của điểm thứ i.
Output
In ra diện tích lớn nhất của đa giác tìm được với độ chính xác 2 chữ số sau dấu thập phân.
Example
Test 1:
Input:
4 3
0 0
2 0
0 3
2 2
Output:
3.00
Test 2:
Input:
4 3
2 0
1 1
1 2
3 1
Output:
1.50
| Được gửi lên bởi: | adm |
| Ngày: | 2013-07-31 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
