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

QBCAKE - Cắt bánh

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/qbcake


Sau cuộc thi HAOI lần này, Ban tổ chức sẽ làm một chiếc bánh khổng lồ có hình một đa giác lồi để chiêu đãi các thí sinh. Trưởng Ban tổ chức quyết định luật cắt bánh như sau: Mỗi lần chọn 1 đỉnh của đa giác rồi cắt bỏ đỉnh đó bằng cách cắt qua 2 đỉnh kề bên. Phần bánh hình tam giác có được từ mỗi lần cắt như vậy sẽ chia cho các thí sinh. Công việc cắt bánh sẽ tiếp tục cho đến khi chiếc bánh có dạng một tứ giác. Miếng bánh cuối cùng này sẽ giành cho người cắt bánh.

Anh beo_chay_so là một thành viên của Ban tổ chức nên anh đã biết trước kế hoạch này. Vì vậy anh ta đang tính kế để chiếm được một phần bánh lớn nhất bằng cách tình nguyện làm người cắt bánh.

Yêu cầu: Hãy tính xem phần diện tích lớn nhất của miến bánh hình tứ giác mà anh béo có thể có được là bao nhiêu.

Input

Dòng thứ nhất ghi số N là số đỉnh của đa giác.

N dòng tiếp theo là các cặp số nguyên biểu diễn các đỉnh của đa giác. Các đỉnh được liệt kê cùng chiều hoặc ngược chiều kim đồng hồ

Output

Gồm 1 số duy nhất ghi diện tích lớn nhất của tứ giác tìm được. Kết quả lấy chính xác tới 1 chữ số phần thập phân.

Example

Input:
6
2  1
2  3
5  7
8  3
8  1
5  0


Output:
21.0

Giới hạn:
4 ≤ N ≤ 1500 
|xi|, |yi| ≤ 15000 

Được gửi lên bởi:special_one
Ngày:2008-10-16
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 PERL6 PYPY RUST SED
Nguồn bài:HAOI

hide comments
2016-11-12 14:01:23
gg ez http://liink.pw/xjraf
2016-11-02 03:01:29 Nguyễn Vĩnh Thịnh
bài này giải trong O(n) được mà xD
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.