HSG8 - A. Hình chữ nhật
Cho n điểm tọa độ nguyên trên mặt phẳng (1 ≤ n ≤ 105). Điểm thứ i (1 ≤ i ≤ n) có tọa độ (xi, yi). Hãy xác định hình chữ nhật có diện tích nhỏ nhất chứa toàn bộ điểm đã cho. Trong đó: 4 đỉnh của hình chữ nhật phải có tọa độ nguyên; các cạnh song song với trục tọa độ và tất cả các điểm phải nằm hoàn toàn bên trong hình chữ nhật đó.
Dữ liệu vào:
Vào từ file văn bản HCN.INP gồm:
- Dòng đầu tiên chứa số n là số điểm tọa độ.
- n dòng tiếp theo chứa các cặp số nguyên là tọa độ của n điểm trên mặt phẳng.
Kết quả ra:
Ghi ra file văn bản HCN.OUT gồm 1 dòng chứa số nguyên là diện tích hình chữ nhật tìm được.
Ví dụ
HCN.INP 4 -1 0 0 1 -1 -1 2 0 HCN.OUT 6
Comments