Tứ giác

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trên hệ trục toạ độ ~Oxy~, cho một đa giác lồi được tạo bởi ~N~ điểm có toạ độ nguyên.

Yêu cầu: Hãy tìm hình tứ giác có diện tích lớn nhất được tạo bởi ~4~ trong ~N~ điểm của đa giác lồi đã cho.

Input

  • Dòng thứ nhất ghi số ~N~ ~(4 \le N \le 10^4)~ là số đỉnh của đa giác lồi;
  • ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ ~(|x|, |y| \le 10^5)~ biểu diễn toạ độ các đỉnh của đa giác. Thứ tự các đỉnh được liệt kê theo chiều kim đồng hồ.

Output

Gồm một số duy nhất là 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 ~1~ chữ số sau phần thập phân.

Ví dụ

Input
5
0 2
1 3
2 2
2 0
0 0
Output
4.0
Giải thích

Chọn các đỉnh: ~(0, 2), (2, 2), (2, 0), (0, 0)~.

Input
6
4 2
3 3
4 5
6 5
7 3
6 2
Output
6.5
Giải thích

Chọn các đỉnh: ~(3, 3), (4, 5), (6, 5), (6, 2)~.

Ràng buộc

  • Có ~40\%~ số test ứng với ~40\%~ số điểm có ~N \le 50~;
  • ~30\%~ số test khác ứng với ~30\%~ số điểm có ~N \le 200~;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 2000~;
  • ~10\%~ số test còn lại ứng với ~10\%~ số điểm không có ràng buộc gì thêm.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.