SRM 490 div2 hard: Hieroglyphs

問題

TopCoder Statistics - Problem Statement

解法

問題の制約から, x 方向, y 方向にずらす候補 dx, dy はそれぞれ -80 から 80 までしかありません。dx, dy としてあり得るものをすべて調べて, それぞれの場合に重なる線分の長さがどれだけになるかを調べれば良いです。

class Hieroglyphs {
public:
    int minimumVisible(vector <string> hier1, vector <string> hier2) {
        vector<pair<pii, pii> > h1, h2;
        int sum = 0;
        for (string s : hier1) {
            for (char& c : s) if (c == ',') c = ' ';
            stringstream ss(s);
            int x1, y1, x2, y2;
            while (ss >> x1 >> y1 >> x2 >> y2) {
                h1.push_back(make_pair(pii(x1, y1), pii(x2, y2)));
                sum += abs(x2-x1) + abs(y2-y1);
            }
        }
        for (string s : hier2) {
            for (char& c : s) if (c == ',') c = ' ';
            stringstream ss(s);
            int x1, y1, x2, y2;
            while (ss >> x1 >> y1 >> x2 >> y2) {
                h2.push_back(make_pair(pii(x1, y1), pii(x2, y2)));
                sum += abs(x2-x1) + abs(y2-y1);
            }
        }
        vector<pii> xrange[100], yrange[100];
        for (auto pp : h1) {
            int x1 = pp.first.first, y1 = pp.first.second;
            int x2 = pp.second.first, y2 = pp.second.second;
            if (x1 == x2) {
                yrange[x1].push_back(pii(y1, y2));
            } else {
                xrange[y1].push_back(pii(x1, x2));
            }
        }
        int minus = 0;
        for (int dx = -80; dx <= 80; dx++) for (int dy = -80; dy <= 80; dy++) {
            int tmp = 0;
            for (auto pp : h2) {
                int x1 = pp.first.first, y1 = pp.first.second;
                int x2 = pp.second.first, y2 = pp.second.second;
                x1 += dx, x2 += dx;
                y1 += dy, y2 += dy;
                if (x1 == x2 && 0 <= x1 && x1 <= 80) {
                    for (auto p : yrange[x1]) {
                        int y3 = p.first, y4 = p.second;
                        if (y3 >= y2 || y4 <= y1) continue;
                        tmp += min(y2, y4) - max(y1, y3);
                    }
                } else if (y1 == y2 && 0 <= y1 && y2 <= 80) {
                    for (auto p : xrange[y1]) {
                        int x3 = p.first, x4 = p.second;
                        if (x3 >= x2 || x4 <= x1) continue;
                        tmp += min(x2, x4) - max(x1, x3);
                    }
                }
            }
            minus = max(minus, tmp);
        }
        return sum-minus;
    }
};