3588. Find Maximum Area of a Triangle

You are given a 2D array coords of size n x 2, representing the coordinates of n points in an infinite Cartesian plane.

Find twice the maximum area of a triangle with its corners at any three elements from coords, such that at least one side of this triangle is parallel to the x-axis or y-axis. Formally, if the maximum area of such a triangle is A, return 2 * A.

If no such triangle exists, return -1.

Note that a triangle cannot have zero area.

class Solution {
public:
    long long maxArea(vector<vector<int>>& coords) {
        pair<long long, long long> x{INT_MAX, INT_MIN}, y{INT_MAX, INT_MIN};
        unordered_map<long long, pair<long long, long long>> xmp, ymp;
        auto udt = [&](pair<long long, long long>& p, long long pos) {
            p.first = min(p.first, pos);
            p.second = max(p.second, pos);
        };
        for(auto& c : coords) {
            long long yp = c[0], xp = c[1];
            udt(x,xp);
            udt(y,yp);
            if(!xmp.count(xp)) xmp[xp] = {INT_MAX, INT_MIN};
            if(!ymp.count(yp)) ymp[yp] = {INT_MAX, INT_MIN};
            udt(xmp[xp], yp);
            udt(ymp[yp], xp);
        }
        long long res = 0;
        for(auto& [dep, pr] : xmp) {
            long long len = pr.second - pr.first;
            long long dif = max(abs(dep - x.first), abs(dep - x.second));
            res = max(res, len * dif);
        }
        for(auto& [dep, pr] : ymp) {
            long long len = pr.second - pr.first;
            long long dif = max(abs(dep - y.first), abs(dep - y.second));
            res = max(res, len * dif);
        }
        return res ? res : -1;
    }
};