Hình chữ nhật (HSG9 - Kontun 2122)
Xem dưới dạng PDFCho \(n\) điểm tọa độ nguyên trên mặt phẳng (\(1 \le N \le 10^5\)). Điểm thứ \(i\) (\(1 \le i \le n\)) có tọa độ (\(x_i\), \(y_i\)), Hãy xác định hình chữ nhật có diện tích nhỏ nhất chứa toàn bộ \(n\) đ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 đó.
Input
- Dòng đầu tiên chứa số \(n\) là số điểm trên tọa độ (\(1 \le N \le 10^5\)).
- \(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.
Output
In ra diện tích hình chữ nhật tìm được.
Sample Input
4
-1 0
0 1
-1 -1
2 0Sample Output
20
Nhận xét
t = int(input()) xMax = -1e9 xMin = 1e9 yMax = -1e9 yMin = 1e9 for i in range(t): x,y = (input()).split() x = int(x) y = int(y) xMax = max(xMax,x) xMin = min(xMin,x) yMax = max(yMax,y) yMin = min(yMin,y) print(str((abs(xMax-xMin)+2)*(abs(yMax-yMin)+2)))
include<bits/stdc++.h>
using namespace std;
int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); long long n; cin >> n; long long xMax = -1e9,yMax = -1e9; long long xMin = 1e9,yMin = 1e9; long long x,y; for(long long i = 0;i<n;i++){ cin >> x >> y; xMax = max(xMax,x); xMin = min(xMin,x); yMax = max(yMax,y); yMin = min(yMin,y); } cout << ((abs(xMax-xMin)+2)*(abs(yMax-yMin)+2)); return 0; }