Frieren and Rotating Calipers Solution

由题矩形长和宽需要与$x$轴或 $y$轴平行

找到最大，最小的$x$， $y$记为$max_x, min_x, max_y, min_y$

答案$(max_x - min_x) * (max_y - min_y)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main(){

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> x(n), y(n);
        for(int i = 0;i < n;i++){
            cin >> x[i] >> y[i];
        }
        int max_x = *max_element(x.begin(), x.end());
        int max_y = *max_element(y.begin(), y.end());
        int min_x = *min_element(x.begin(), x.end());
        int min_y = *min_element(y.begin(), y.end());
        cout << (max_x - min_x) * (max_y - min_y) << "\n";
    }

    return 0;
}

复杂度$O(T * n)$

杂记

学习旋转卡壳时想到的签到题，赛时凡过题者都过了这题