Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKPOLY - Chia đa giác

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkpoly


Đứ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á 106.

Ví dụ

Dữ liệu:
5
0 0
0 2
1 4
2 2
2 0

Kết qủa
4.0
2.0

Được gửi lên bởi:Jimmy
Ngày:2007-12-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:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:IOICamp Marathon 2005-2006

hide comments
2018-05-13 19:00:51 Vu Duy Truc
Lúc đầu nghĩ là khó. Nhìn lại N<200. Kết luận luôn k khó nữa. N^3 chạy thỏa mái.
Đang suy nghĩ thử có cách nào lẹ hơn không
2018-01-09 16:07:37
Xin sol
2016-02-04 13:29:38
http://ouo.io/Zt5wz
2015-11-19 16:23:25
qhd thoi@@
2014-09-16 04:28:54 Thcs Ðặng Chánh Kỷ
mat 1 sang 1 dem,bai hay
2014-08-13 17:00:52 Nắng
giảm time phê 5.55 quá đẹp =)))

Last edit: 2014-08-13 17:01:20
2014-08-06 17:58:06 Anh Duc Le
để Input số thực mới AC. Why ???
2014-02-23 08:27:30 Hướng Thái Dương
ps đã nói rõ rồi Các tọa độ là các số nguyên có trị tuyệt đối không quá 10^6.

Last edit: 2014-02-23 08:28:15
2014-02-08 13:44:50 a;slkfjasl;fkj
Đừng nghe theo mấy comment ở dưới nhé, tọa độ kiểu nguyên :3

Last edit: 2014-02-08 17:14:17
2012-12-01 02:02:40  日本語
abc
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.