VM3SETS - Người yêu hòa bình

Giới hạn
  • Thời gian: 0.6s
  • 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.

Link đọc đề trên VNOJ

Ngày xửa ngày xửa, quần đảo của Pirate bị chia cắt bởi các thế lực cát cứ. Cuối cùng, có 3 thế lực mạnh nhất đã thâu tóm hết các nước lân bang để tạo thành thế Tam Đảo: đó là nước Rỉ, nước Quá và nước Đanh. Giữa ba nước này cứ diễn ra chọi dừa liên miên khiến dân chúng u đầu mẻ trán như cơm bữa, cuộc sống lầm than không sao kể xiết.

Pirate sinh ra trong thời loạn, xuất thân từ một gia đình trồng chuối, từ nhỏ đã nối tiếng với tài vừa xem đá bóng vừa... làm thơ. Thấy con trai mình có tài văn chương thiên bẩm, phụ thân Pirate mời cả "Bắc Cương, Nam Vũ" đến dạy chữ cho anh, những mong sau này con trai có thể trở thành một nhà thuyết khách, đi khắp Tam Đảo giảng hòa ba nước, tạo phúc cho bá tánh.

Sao bao nhiêu sóng gió, cuối cùng, bằng việc hứa sẽ truyền cho các chúa đảo về bí quyết trồng chuối to, Pirate đã đạt được một thỏa thuận hòa bình cho Tam Đảo. Đó là sự hình thành một "vùng ngừng chọi". Pirate kéo tấm bản đồ các hòn đảo trong quần đảo ra. Ở trên đó, mỗi đảo được kí hiệu bởi một điểm nguyên trên mặt phẳng tọa độ và bị duy nhất một trong ba nước chiếm giữ. "Vùng ngừng chọi" sẽ có hình dạng một tam giác với ba đỉnh là ba hòn đảo trên tấm bản đồ này mà trong đó không có hai hòn đảo nào bị chiếm giữ bởi cùng một nước. Ba nước cam đoan sẽ không chọi dừa trong phần diện tích che phủ bởi "vùng ngừng chọi".

Pirate chỉ muốn "vùng ngừng chọi" có diện tích lớn nhất để bá tánh bớt lầm than và có thể chăm lo trồng chuối. Hãy giúp anh ấy xác định diện tích lớn nhất có thể của "vùng ngừng chọi"!

Input

Input gồm:

  • Dòng thứ nhất là số nguyên N, số đảo mà mỗi nước chiếm giữ (cả ba nước đều chiếm được cùng một số lượng đảo).
  • Tiếp theo là một dòng trống.
  • N dòng tiếp theo, mỗi dòng là hai số nguyên x y, thể hiện vị trí của một hòn đảo thuộc về nước Rỉ.
  • Tiếp theo là một dòng trống.
  • N dòng tiếp theo, mỗi dòng là hai số nguyên x y, thể hiện vị trí của một hòn đảo thuộc về nước Quá.
  • Tiếp theo là một dòng trống.
  • N dòng tiếp theo, mỗi dòng là hai số nguyên x y, thể hiện vị trí của một hòn đảo thuộc về nước Đanh.

Output

Output gồm một dòng duy nhất là diện tích lớn nhất của "vùng ngừng chọi" tìm được (in ra một chữ số sau dấu phẩy).

Example 

Input:
5

0 0
-8 0
3 0
6 2
-3 8

-5 -7
2 0
-1 0
8 0
4 -2

0 6
-1 -2
4 -4
-5 -4
2 -5
Output:
74.0

Giải thích: "vùng ngừng chọi" có các đỉnh tại (-3, 8), (8, 0), (-5, -4).

Giới hạn

  • 1 ≤ N ≤ 10 5
  • Trong 50% số test có 1 ≤ N ≤ 200
  • Các điểm có tọa độ là số nguyên có trị tuyệt đối không quá 10 9 .

  • Người up: voj