[VTT Q4 Contest 07] Bài 1: Hình chữ nhật [RECT]
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
RECT.INP
Output:
RECT.OUT
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, PyPy, Python
Trên mặt phẳng tọa độ cho ~n~ điểm có tọa độ nguyên ~A_1(x_1, y_1), A_2(x_2, y_2), \dots, A_n(x_n, y_n)~.
Hãy tìm hình chữ nhật có các cạnh song song với hai trục tọa độ, chứa tất cả ~n~ điểm đã cho (điểm được phép nằm trên cạnh của hình chữ nhật) và có diện tích nhỏ nhất. In ra diện tích đó.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^6~), số điểm.
- ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i~ và ~y_i~ (~-10^9 \le x_i, y_i \le 10^9~), là tọa độ của điểm thứ ~i~.
Kết quả
- In ra một số duy nhất là diện tích nhỏ nhất của hình chữ nhật tìm được.
Ví dụ
RECT.INP
5
0 0
1 1
3 -2
-2 -1
2 -1
RECT.OUT
15
Giải thích: Hình chữ nhật nhỏ nhất có đỉnh trái dưới là ~(-2, -2)~ và đỉnh phải trên là ~(3, 1)~, tức rộng 5 và cao 3, diện tích bằng 15.
Bình luận