座標圧縮を勉強しました

知識の足り無さを実感しては勉強っていう感じ...

(解いてた問題のソースコード)https://joi2008ho.contest.atcoder.jp/submissions/1990295

誤植がいっぱいありそうだけど自分のメモ的に

座標圧縮の順序

1.座標上にある長方形などの点を取得する

いつも通りとってやればOK

2.座標ごとに振り分ける

僕は心配性だったので、

長方形の始点と終点を別々に記録しなければならないのかと思っていましたが

圧縮して取り出すために、始点と終点を追加していきます

for(int i = 0;i < n;i++)
{
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;

    xs[i] = x1;
    ys[i] = y1;
    xe[i] = x2;
    ye[i] = y2;

    X.push_back(x1);
    X.push_back(x2);
    Y.push_back(y1);
    Y.push_back(y2);
}

x座標はXに、y座標はY座標に入れていく

3.座標の隅の座標を追加する

これ重要

座標全体を圧縮するので、座標の始点と終点は必ず必要(これでWA出して泣いてた)

X.push_back(0);
Y.push_back(0);
X.push_back(w);
Y.push_back(h);

4.圧縮する

これ定石みたいなので覚えるしか無い

sort(X.begin(),X.end());
sort(Y.begin(),Y.end());

X.erase(unique(X.begin(),X.end()),X.end());
Y.erase(unique(Y.begin(),Y.end()),Y.end());

for(int i = 0;i < n;i++)
{
    int x1 = lower_bound(X.begin(),X.end(),xs[i]) - X.begin();
    int x2 = lower_bound(X.begin(),X.end(),xe[i]) - X.begin();

    int y1 = lower_bound(Y.begin(),Y.end(),ys[i]) - Y.begin();
    int y2 = lower_bound(Y.begin(),Y.end(),ye[i]) - Y.begin();

    imos[x1][y1]++;
    imos[x2][y2]++;
    imos[x1][y2]--;
    imos[x2][y1]--;
}

lower_boundを使って圧縮していく感じ

以上！