Cắt bánh

View as PDF

Submit solution

Points: 0.81 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
HAOI
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 beochayso 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~ (~4 \leq N \leq 1500~) là số đỉnh của đa giác.

~N~ dòng tiếp theo là các cặp số nguyên (~|x_{i}|, |y_i| \leq 15000~) 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.

Sample Input

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

Sample Output

21.0

Comments

Please read the guidelines before commenting.


There are no comments at the moment.