Tóm tắt đề bài

Cho ~n~ điểm ~(x_i, y_i)~ trên mặt phẳng tọa độ. Hãy tìm hình chữ nhật diện tích nhỏ nhất chứa cả ~n~ điểm này.

Lời giải

Hình chữ nhật tối ưu sẽ luôn có một (vài) điểm nằm trên cạnh. Nếu không có điểm nào nằm trên cạnh, ta hoàn toàn có thể hạ độ dài cạnh mà không làm ảnh hưởng kết quả.

Vì vậy, ta gọi ~min_x~ là ~min (x_i)~ với ~1 \le i \le n~. Tương tự ta có ~max_x~, ~min_y~ và ~max_y~.

Đây là các tọa độ tối thiểu và tối đa của các cạnh hình chữ nhật. Vì vậy, diện tích tối thiểu của hình chữ nhật là ~(max_x - min_x) \times (max_y - min_y)~.