首先理解题意,要求最小面积的正方形,其实就是找到一个正方形,能恰好把所有的点框住,并求出这个正方形的面积。

那么边输入数据边更新所有坐标的边界条件,最后再计算面积即可。

#include <climits>
#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        int maxX = INT_MIN, minX = INT_MAX;
        int maxY = INT_MIN, minY = INT_MAX;
        int xi, yi;
        // 更新最大最小横纵坐标
        for (int i = 0; i < n; i++) {
            cin >> xi >> yi;
            maxX = max(maxX, xi);
            minX = min(minX, xi);
            maxY = max(maxY, yi);
            minY = min(minY, yi);
        }
        // 计算横纵坐标差值
        int xDiff = maxX - minX;
        int yDiff = maxY - minY;
        // 计算最小面积
        cout << max(xDiff * xDiff, yDiff * yDiff) << endl;
    }
    return 0;
}

时间复杂度:O(n),遍历输入的数据

空间复杂度:O(1),仅使用了几个变量