AIO 2021 Q2: Art Class II - Late Night Code

Contest Source: AIO 2021

In order to find the minimum area rectangle, we observe that the lowest upper edge we can get must be in line with the top-most hole. Similarly, the highest bottom edge must be the bottom-most hole, the left-most right edge must be on the right-most hole, and the right-most left edge must be on the left-most hole. Hence, this problem simply becomes a problem of finding the minimum and maximum \(x\) and \(y\) coordinates, and using them to construct the sides of the rectangle. Afterwards, we can trivially calculate the area. The complexity is \(O(N)\)

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

#define MAXN 100005

int main () {
    freopen("artin.txt", "r", stdin);
    freopen("artout.txt", "w", stdout);

    int N;
    cin >> N;

    // the edges of our rectangle
    int u = 0;
    int d = INT_MAX;
    int l = INT_MAX;
    int r = 0;

    // find the min and max of the x and y coordinates separately
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        u = max(u, y);
        d = min(d, y);
        l = min(l, x);
        r = max(r, x);
    }
    // u,d,l,r now define the four sides of our rectangle

    // print out the area
    int area = (r - l) * (u - d);
    printf("%d\n", area);
}