Hướng dẫn giải

Cần tìm hình chữ nhật có cạnh song song với trục tọa độ, chứa mọi điểm và có diện tích nhỏ nhất. Đây là bài rất đơn giản: chỉ cần tìm tọa độ nhỏ nhất và lớn nhất theo mỗi trục.

Sub 1: Công thức — ~O(n)~

Hình chữ nhật nhỏ nhất chứa mọi điểm có hai cạnh dọc nằm tại ~x_{\min}~ và ~x_{\max}~, hai cạnh ngang nằm tại ~y_{\min}~ và ~y_{\max}~. Diện tích là ~(x_{\max} - x_{\min}) \cdot (y_{\max} - y_{\min})~. Nếu ~n = 1~ thì diện tích bằng 0 (công thức vẫn đúng).

Lưu ý: mỗi chiều có thể dài tới ~2 \cdot 10^9~ nên tích tới ~4 \cdot 10^{18}~, phải dùng long long (vẫn chưa tràn). Với ~n~ tới ~10^6~ dòng nên tắt đồng bộ cin. Bài không có cách vét cạn hợp lý hơn công thức này nên chỉ có 1 sub: đúng 20/20 test.

Chương trình hoàn chỉnh

main mở file RECT.INP/RECT.OUT rồi gọi sub1 duy nhất.

#include <bits/stdc++.h>
using namespace std;

// Bài này chỉ có một cách làm tự nhiên (một công thức), nên chỉ có 1 sub.
void sub1() {
    int n;
    cin >> n;
    long long mnx = LLONG_MAX, mxx = LLONG_MIN, mny = LLONG_MAX, mxy = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        mnx = min(mnx, x); mxx = max(mxx, x);
        mny = min(mny, y); mxy = max(mxy, y);
    }
    // Chiều rộng * chiều cao, tối đa 2e9 * 2e9 = 4e18 vẫn nằm trong long long
    cout << (mxx - mnx) * (mxy - mny) << "\n";
}

int main() {
    freopen("RECT.INP", "r", stdin);
    freopen("RECT.OUT", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    sub1();
}