\(N\) con bò của Farmer John (\(3 \leq N \leq 50\,000\)) đều đứng tại các vị trí phân biệt trên cánh đồng hai chiều của ông. FJ muốn bao quanh tất cả đàn bò bằng một hàng rào hình chữ nhật có các cạnh song song với trục \(x\) và trục \(y\), đồng thời muốn hàng rào này nhỏ nhất có thể nhưng vẫn chứa mọi con bò (bò được phép đứng trên biên).

Không may, FJ đang có ngân sách eo hẹp vì sản lượng sữa thấp trong quý trước. Do đó, nếu có thể, ông muốn xây một khu vực có hàng rào bao quanh còn nhỏ hơn nữa và sẵn sàng bán một con bò trong đàn để thực hiện điều này.

Hãy giúp FJ tính diện tích nhỏ nhất có thể bao quanh bằng hàng rào sau khi loại một con bò khỏi đàn (rồi xây hàng rào khít nhất bao quanh \(N-1\) con bò còn lại).

Trong bài này, hãy coi bò là các điểm và hàng rào là tập hợp gồm bốn đoạn thẳng (tức là đừng coi bò là các "hình vuông đơn vị"). Lưu ý rằng đáp án có thể bằng không, chẳng hạn nếu tất cả những con bò còn lại cùng đứng trên một đường thẳng đứng hoặc ngang. Cuối cùng, vì \(N\) có thể khá lớn, bạn có thể cần cẩn thận khi giải bài để bảo đảm chương trình chạy đủ nhanh!

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên xác định vị trí của một con bò. Tọa độ của bò là các số nguyên dương trong khoảng \(1 \ldots 40\,000\).

Dữ liệu ra

In một số nguyên duy nhất biểu thị diện tích nhỏ nhất mà FJ có thể bao quanh bằng hàng rào sau khi loại khỏi đàn một con bò được lựa chọn cẩn thận.

Ví dụ

4
2 4
1 1
5 2
17 25

12

Nguồn

USACO 2016 US Open Contest, Bronze - Field Reduction: https://usaco.org/index.php?page=viewproblem2&cpid=641

Tác giả: Brian Dean.