Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-01

Intersect

| 18:34

問題文

全ての矩形に囲まれる矩形の面積を求める。

class Intersect {
public:
    int area(vector <int> x, vector <int> y) {
        int left =INT_MIN, right=INT_MAX;
        int upper=INT_MIN, lower=INT_MAX;
        for (int i = 0; i < x.size(); i += 2) {
            if (x[i] > x[i+1]) swap(x[i], x[i+1]);
            if (y[i] > y[i+1]) swap(y[i], y[i+1]);
            left  = max(left, x[i]);
            right = min(right, x[i+1]);
            upper = max(upper, y[i]);
            lower = min(lower, y[i+1]);
        }
        if ((right-left) <= 0 || (lower-upper) <= 0) return 0;
        else return (right-left) * (lower-upper);
    }
};