NKPOLY - Chia đa giác
Giới hạn- Thời gian: 0.142s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đức vua vương quốc XYZ tổ chức kén rể cho cô công chúa duy nhất của mình. Vì vậy, ông đặt ra những yêu cầu rất cao cho con rể tương lai. Để có thể trở thành con rể của ngài, các chàng trai thi nhau thể hiện mình. Sau khi vượt qua những phần thi đòi hỏi sức khoẻ, lòng dũng cảm, … họ sẽ gặp phải một thử thách vô cùng khó khăn, đó là phần thi về sự nhanh nhạy và thông minh. Đức vua sẽ cho mỗi người một miếng bìa hình đa giác lồi N đỉnh. Đức vua yêu cầu các chàng trai vẽ N-3 đường chéo bất kì sao cho 2 đường chéo bất kì không có điểm chung khác các đầu mút. Với cách vẽ như vậy, chúng ta sẽ thu được N-2 hình tam giác. Đức vua yêu cầu họ hãy tìm 2 cách chia:
- Một cách chia sao cho tam giác có diện tích lớn nhất trong N-2 tam giác là lớn nhất.
- Một cách chia sao cho tam giác có diện tích lớn nhất trong N-2 tam giác là nhỏ nhất.
Sau khi nhà vua đưa ra hình dạng của đa giác lồi, họ sẽ chỉ có 1 giây để đưa ra đáp án của mình. Người đưa ra đáp án đúng nhất và nhanh nhất sẽ được chọn làm phò mã. Bạn cũng là một người đã lọt vào vòng thi này. Hãy chứng tỏ khả năng của mình đi!
Dữ liệu
- Dòng đầu tiên ghi số nguyên N là số đỉnh của đa giác.
- Trong n dòng sau, mỗi dòng ghi một cặp số nguyên là tọa độ các đỉnh của đa giác. Các đỉnh được liệt kê theo chiều kim đồng hồ.
Kết qủa
- Dòng thứ nhất ghi diện tích của tam giác lớn nhất trong trường hợp 1.
- Dòng thứ hai ghi diện tích của tam giác lớn nhất trong trường hợp 2.
Các giá trị diện tích có độ chính xác 1 chữ số thập phân.
Giới hạn
- 4 ≤ N ≤ 200.
- Các tọa độ là các số nguyên có trị tuyệt đối không quá 10 6 .
Ví dụ
Dữ liệu: 5 0 0 0 2 1 4 2 2 2 0 Kết qủa 4.0 2.0
- Người up: paulmcvn
- Nguồn bài: IOICamp Marathon 2005-2006