13167번: 포스터

https://www.acmicpc.net/problem/13167

한 포스터가 다른 포스터를 가릴 수 있을 때, 각 포스터가 보이는 부분의 넓이를 구하는 문제이다.

포스터의 꼭지점 좌표를 압축하면 2n * 2n 격자 모양으로 만들 수 있다. 이렇게 만든 격자를 왼쪽에서부터 한 열씩 본다. 어떤 포스터의 세로 구간 내에 포스터가 붙지 않은 영역 넓이 계산 및 포스터를 붙임 체크는 Union-find 자료 구조로 빠르게 처리할 수 있다. 현재 보고 있는 열에서 가장 나중에 붙인 포스터부터 붙여 보며 각 포스터마다 보이는 영역 넓이를 누적시켜준다.

시간복잡도는 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, sx[5000], sy[5000], ex[5000], ey[5000], p[10000], ix[10000], iy[10000];
long long res[5000];
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", sx + i, sy + i, ex + i, ey + i);
        ix[i] = sx[i]; ix[i + n] = ex[i];
        iy[i] = sy[i]; iy[i + n] = ey[i];
    }
    sort(ix, ix + 2 * n);
    sort(iy, iy + 2 * n);
    for (int i = 0; i < n; i++) {
        sx[i] = lower_bound(ix, ix + 2 * n, sx[i]) - ix;
        ex[i] = lower_bound(ix, ix + 2 * n, ex[i]) - ix;
        sy[i] = lower_bound(iy, iy + 2 * n, sy[i]) - iy;
        ey[i] = lower_bound(iy, iy + 2 * n, ey[i]) - iy;
    }
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++) p[j] = j;
        for (int j = n; j--;) if (sx[j] <= i && i < ex[j])
            for (int k = f(sy[j]); k < ey[j]; k = p[f(k)] = f(k + 1))
                res[j] += 1LL * (ix[i + 1] - ix[i])*(iy[k + 1] - iy[k]);
    }
    for (int i = 0; i < n; i++) printf("%lld\n", res[i]);
    return 0;
}

4223번: Mummy Madness

https://www.acmicpc.net/problem/4223


시간복잡도는 테스트 케이스마다 $O(n\lg L * (\lg L+\lg n))$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MX = 1e6;
struct st {
    int x, l, r, c;
}line[200000];
int n, x[100000], y[100000], len[MX * 8], cnt[MX * 8];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (gr < l || r < gl) return;
    if (gl <= l&&r <= gr) cnt[h] += x;
    else update(h * 2 + 1, l, (l + r) / 2, gl, gr, x), update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    len[h] = cnt[h] ? r - l + 1 : l^r ? len[h * 2 + 1] + len[h * 2 + 2] : 0;
}
bool f(int t) {
    int sz = 0;
    for (int i = 0; i < n; i++) {
        int sx = max(x[i] - t, MX - t), ex = min(x[i] + t, MX + t),
            sy = max(y[i] - t, MX - t), ey = min(y[i] + t, MX + t);
        if (sx > ex || sy > ey) continue;
        line[sz++] = { sx,sy,ey,1 };
        line[sz++] = { ex + 1,sy,ey,-1 };
    }
    sort(line, line + sz, [](st i, st j) {return i.x < j.x; });
    long long area = 0;
    for (int i = 0; i < sz; i++) {
        if (i) area += 1LL * len[0] * (line[i].x - line[i - 1].x);
        update(0, 0, MX * 2 + 1, line[i].l, line[i].r, line[i].c);
    }
    return area < 4LL * t*t + 4 * t + 1;
}
int main() {
    for (int t = 1; scanf("%d", &n), ~n; t++) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", x + i, y + i);
            x[i] += MX;
            y[i] += MX;
        }
        int low = 0, up = MX, mid;
        while (low <= up) {
            mid = (low + up) / 2;
            f(mid) ? low = mid + 1 : up = mid - 1;
        }
        printf("Case %d: ", t);
        low > MX ? puts("never") : printf("%d\n", low);
    }
    return 0;
}

4004번: 쿠나이

https://www.acmicpc.net/problem/4004

풀이는 아래 링크로 대체한다.
https://algospot.com/wiki/old/232/APIO2012

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define idx(u,v) (gd[(u)/2][0]*x[v]+gd[(u)/2][1]*y[v])
#define pos(u) (2*x[u]-y[u])
#define dis(u,v) (abs(x[u]-x[v])+abs(y[u]-y[v]))
const int MXN = 1e5, dx[] = { 0,-1,0,1 }, dy[] = { 1,0,-1,0 }, fd[][3] = { { 0,7,11 },{ 1,3,9 },{ 2,5,10 },{ 4,6,8 } }, gd[][2] = { { 1,-1 },{ 1,1 },{ 1,-1 },{ 1,1 },{ 0,1 },{ 1,0 } };
map<int, map<int, int> > mc[12];
priority_queue<pair<int, pair<int, int> > > pq;
int x[MXN], y[MXN], d[MXN], w, h, n, ev[MXN], lt[MXN * 8], ct[MXN * 8];
long long res;
struct st { int l, r, p, c; };
vector<st> line;
vector<int> cd;
int find(int u, int v) {
    auto &mp = mc[u ^ 1][idx(u, v)];
    auto it = mp.upper_bound(pos(v));
    if (u & 1) {
        if (it == mp.begin()) return -1;
        return (--it)->second;
    }
    return it == mp.end() ? -1 : it->second;
}
void add(int t, int i) {
    if (!~i || t == ev[i]) return;
    ev[i] = t;
    int sx = x[i], sy = y[i], ex = sx + t / 2 * dx[d[i]], ey = sy + t / 2 * dy[d[i]];
    if (sx > ex) swap(sx, ex);
    if (sy > ey) swap(sy, ey);
    sx = max(sx, 1);
    sy = max(sy, 1);
    ex = min(ex, h) + 1;
    ey = min(ey, w) + 1;
    line.push_back({ sx,ex,sy,1 });
    line.push_back({ sx,ex,ey,-1 });
    cd.push_back(sx);
    cd.push_back(ex);
    for (int it : fd[d[i]]) {
        int h = find(it, i), t;
        if (~h) {
            mc[it][idx(it, i)].erase(pos(i));
            t = find(it ^ 1, h);
            if (~t) pq.push({ -dis(h, t), make_pair(h, t) });
        }
    }
}
void update(int h, int l, int r, int gl, int gr, int c) {
    if (r < gl || gr < l) return;
    if (gl <= l&&r <= gr) ct[h] += c;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, c);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, c);
    }
    lt[h] = ct[h] ? cd[r + 1] - cd[l] : l^r ? lt[h * 2 + 1] + lt[h * 2 + 2] : 0;
}
int main() {
    scanf("%d%d%d", &w, &h, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", y + i, x + i, d + i);
        pq.push({ -2e9, make_pair(i,-1) });
        ev[i] = 2e9 + 1;
    }
    for (int i = 0; i < n; i++) for (int it : fd[d[i]]) {
        int t = find(it, i);
        if (~t) pq.push({ -dis(i,t), make_pair(i,t) });
        mc[it][idx(it, i)][pos(i)] = i;
    }
    while (!pq.empty()) {
        int t = -pq.top().first;
        pair<int, int> p = pq.top().second;
        pq.pop();
        if (ev[p.first] < t || ~p.second && ev[p.second] < t) continue;
        add(t, p.first);
        add(t, p.second);
    }
    sort(cd.begin(), cd.end());
    cd.erase(unique(cd.begin(), cd.end()), cd.end());
    sort(line.begin(), line.end(), [](st u, st v) {return u.p < v.p; });
    for (int i = 0; i < line.size(); i++) {
        if (i) res += 1LL * (line[i].p - line[i - 1].p)*lt[0];
        update(0, 0, cd.size() - 1, lower_bound(cd.begin(), cd.end(), line[i].l) - cd.begin(),
            lower_bound(cd.begin(), cd.end(), line[i].r) - cd.begin() - 1, line[i].c);
    }
    printf("%lld", res);
    return 0;
}

11000번: 강의실 배정

https://www.acmicpc.net/problem/11000


$O(n\lg n)$

모든 강의에 대해 [시작,끝) 구간을 나타내는 선분을 만들어보자.
앞에서부터 라인 스위핑을 할 때, 최대로 교차되는 선분 개수가 답이다.

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int, int> p[400000];
int n, r;
int main() {
    scanf("%d", &n);
    for (int i = 0, s, t; i < n; i++) {
        scanf("%d%d", &s, &t);
        p[i] = { s,1 };
        p[i + n] = { t,-1 };
    }
    sort(p, p + 2 * n);
    for (int i = 0, s = 0; i < 2 * n; i++) r = max(r, s += p[i].second);
    printf("%d", r);
    return 0;
}

1666번: 최대 증가 직사각형 집합

https://www.acmicpc.net/problem/1666


$O(n\lg n)$

시작점과 끝점의 y 성분을 가지고 최댓값을 리턴하는 세그먼트 트리를 만들 것이다.
시작점과 끝점을 x를 기준으로 오름차순 정렬한 다음 앞에서부터 본다. 같은 x 값이면 시작점이 끝점보다 앞서야 한다.
i) 시작점
세그먼트 트리에서 현재 점의 y 좌표보다 작은 구간에 대해 최댓값을 구한다.
해당 값 + 1은 현재 직사각형을 포함하고 현재 점보다 왼쪽 아래에 있는 직사각형들을 포함한 집합 L의 최대 크기가 된다.
이를 따로 저장해놓는다.
ii) 끝점
앞서 시작점을 스위핑하면서 구한 최댓값+1을 세그먼트 트리에서 현재 점 y 좌표에 갱신해준다.

답은 저장해놓은 L의 최대 크기가 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, c[MXN], tree[MXN * 4], y[MXN], res;
struct st {
    int x, y, t, idx;
}p[MXN * 2];
void update(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    tree[h] = max(tree[h], x);
    if (l^r) {
        update(h * 2 + 1, l, (l + r) / 2, g, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
    }
}
int query(int h, int l, int r, int g) {
    if (g < l) return 0;
    if (r <= g) return tree[h];
    return max(query(h * 2 + 1, l, (l + r) / 2, g), query(h * 2 + 2, (l + r) / 2 + 1, r, g));
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &p[i].x, &p[i].y, &p[i + n].x, &p[i + n].y);
        p[i].idx = p[i + n].idx = i;
        p[i].t = 1;
        y[i] = p[i + n].y;
    }
    sort(p, p + 2 * n, [](st i, st j) {return i.x<j.x || i.x == j.x&&i.t>j.t; });
    sort(y, y + n);
    for (int i = 0; i < 2 * n; i++) {
        int lb = lower_bound(y, y + n, p[i].y) - y;
        if (p[i].t) res = max(res, c[p[i].idx] = query(0, 0, n - 1, lb - 1) + 1);
        else update(0, 0, n - 1, lb, c[p[i].idx]);
    }
    printf("%d", res);
    return 0;
}

12771번: Oil

https://www.acmicpc.net/problem/12771


$O(n^2\lg n)$

답에 해당하는 시추드릴이 나타내는 직선을 그렸을 때, 언제나 이 직선이 관통하고 있는 석유층 중 하나의 왼쪽 끝 지점에 닿도록 평행이동시킬 수 있다.
따라서 답은 어느 한 석유층의 왼쪽 끝점을 지나는 직선을 그을 때 관통하는 최대 석유층 개수라고 보아도 된다.

이제 i번 석유층의 왼쪽 끝지점 u를 지나는 직선을 그을 때 관통할 수 있는 최대 석유층 개수를 구해보자.
u를 지나는 석유층과 평행한 직선 l을 생각하고 이를 u를 회전축으로 반시계 방향으로 회전시키는 모습을 상상해보자.
모든 석유층은 l이 회전함에 따라 관통하기 시작했다가 다시 관통하지 않게 될 것이다.
즉, 석유층(i)마다 l이 해당 석유층을 관통하는 l의 회전각 구간 [xi, yi]을 표현할 수 있고
한 지점에서 해당 구간들이 가장 많이 겹칠 때 그 개수가 답이 된다.

* 최대로 많이 겹칠 때 개수를 구하는 방법은 https://www.acmicpc.net/problem/11000 문제 풀이와 동일하다.

이를 구현할 때는 회전각을 이용하는 것보다 ccw 공식을 통해 상대적인 회전 정도를 비교하는 편이 계산 정확도면에서 훨씬 좋다.
먼저, u와 같은 y값을 가진 석유층을 제외하고 u보다 y값이 작은 양 끝점들은 u에 대해 점대칭 시킨다.
그리고 나서 ccw공식을 이용하여 각 점들을 반시계 방향으로 정렬시킨다.
이제 정렬된 순서대로 들어오는 점들에 대해 선분 왼쪽 끝점이면 석유량을 증가시키고, 오른쪽 끝점이면 가중치를 차감시키면서 최대 누적량을 구한다.

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int MXN = 2e3;
typedef long long ll;
int n, r;
pair<ll, ll> o;
struct st {
    pair<ll, ll> t;
    int v;
    bool operator<(st i) const {
        ll ccw = (t.x - o.x)*(i.t.y - o.y) - (t.y - o.y)*(i.t.x - o.x);
        return ccw<0 || !ccw&&v>i.v;
    }
}p[MXN * 2], q[MXN * 2];
int main() {
    scanf("%d", &n);
    for (int i = 0, x0, x1, y; i < n; i++) {
        scanf("%d%d%d", &x0, &x1, &y);
        p[i] = { { min(x0,x1),y },abs(x0 - x1) };
        p[i + n] = { { max(x0,x1),y },-abs(x0 - x1) };
    }
    for (int i = 0; i < n; i++) {
        int sz = 0, s = p[i].v;
        o = p[i].t;
        for (int j = 0; j < 2 * n; j++) {
            if (o.y < p[j].t.y) q[sz++] = p[j];
            if (o.y > p[j].t.y) q[sz++] = { { 2 * o.x - p[j].t.x,2 * o.y - p[j].t.y },-p[j].v };
        }
        sort(q, q + sz);
        for (int j = 0; j < sz; j++) r = max(r, s += q[j].v);
        r = max(r, s);
    }
    printf("%d", r);
    return 0;
}

3392번: 화성 지도

https://www.acmicpc.net/problem/3392


$O(n\lg L)$

plane sweeping
http://codedoc.tistory.com/421

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e4, MXL = 3e4;
int n, lt[MXL * 4], ct[MXL * 4], res;
struct st {
    int x, y1, y2, s;
}l[MXN * 2];
void update(int h, int l, int r, int gl, int gr, int s) {
    if (r < gl || gr < l) return;
    if (gl <= l && r <= gr) ct[h] += s;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, s);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, s);
    }
    lt[h] = !ct[h] ? l^r ? lt[h * 2 + 1] + lt[h * 2 + 2] : 0 : r - l + 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x1, y1, x2, y2; i < n; i++) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        l[i] = { x1,y1,y2 - 1,1 };
        l[i + n] = { x2,y1,y2 - 1,-1 };
    }
    sort(l, l + 2 * n, [](st i, st j) {return i.x < j.x; });
    for (int i = 0; i < 2 * n; i++) {
        if (i) res += lt[0] * (l[i].x - l[i - 1].x);
        update(0, 0, MXL - 1, l[i].y1, l[i].y2, l[i].s);
    }
    printf("%d", res);
    return 0;
}

7626번: 직사각형

https://www.acmicpc.net/problem/7626


$O(n\lg n)$

http://codedoc.tistory.com/421

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MXN = 2e5;
int n, idx[MXN * 2], e, lt[MXN * 8], ct[MXN * 8];
ll res;
struct st {
    int x, y1, y2, t;
}line[MXN * 2];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (r < gl || gr < l) return;
    if (gl <= l && r <= gr) ct[h] += x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    }
    if (ct[h]) lt[h] = idx[r + 1] - idx[l];
    else lt[h] = l^r ? lt[h * 2 + 1] + lt[h * 2 + 2] : 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x1, x2, y1, y2; i < n; i++) {
        scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
        line[i] = { x1,y1,y2,1 };
        line[i + n] = { x2,y1,y2,-1 };
        idx[i] = y1;
        idx[i + n] = y2;
    }
    sort(line, line + 2 * n, [](st i, st j) {return i.x < j.x; });
    sort(idx, idx + 2 * n);
    e = unique(idx, idx + 2 * n) - idx;
    for (int i = 0; i < 2 * n; i++) {
        if (i) res += (ll)lt[0] * (line[i].x - line[i - 1].x);
        update(0, 0, e - 1, lower_bound(idx, idx + e, line[i].y1) - idx,
            lower_bound(idx, idx + e, line[i].y2) - idx - 1, line[i].t);
    }
    printf("%lld", res);
    return 0;
}

2601번: 도서실카펫

https://www.acmicpc.net/problem/2601


$O(nlgln)$ // 좌표압축을 통해 O(nlgn)으로 해결 가능

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5, MAX_L = 1e6;
int dx, dy, ux, uy, l, n, scnt, r, sum[MAX_L * 4], maxi[MAX_L * 4];
struct st {
    int y, x1, x2, t;
    bool operator<(st i) const {
        return y < i.y || y == i.y&&t<i.t;
    }
}s[MAX_N * 2];
void push(int x1, int y1, int x2, int y2) {
    x2 = max(x2, l - 1);
    y2 = max(y2, l - 1);
    if (x1>x2 || y1>y2) return;
    s[scnt++] = { y1,x1,x2,1 };
    s[scnt++] = { y2 + 1,x1,x2,-1 };
}
void query(int h, int l, int r, int gl, int gr, int x) {
    if (gr < l || r < gl) return;
    if (gl <= l && r <= gr) sum[h] += x;
    else {
        query(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
        query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    }
    maxi[h] = l == r ? sum[h] : sum[h] + max(maxi[h * 2 + 1], maxi[h * 2 + 2]);
}
int main() {
    scanf("%d %d %d %d %d %d", &dy, &ux, &uy, &dx, &l, &n);
    for (int i = 0, x, y, z, w; i < n; i++) {
        scanf("%d %d %d %d", &x, &y, &z, &w);
        push(y - 1, z - 1, w + l - 1, x + l - 1);
    }
    sort(s, s + scnt);
    for (int i = 0; i < scnt; i++) {
        query(0, dx, ux, s[i].x1, s[i].x2, s[i].t);
        r = max(r, maxi[0]);
    }
    printf("%d", r);
    return 0;
}

2185번: 직사각형의 합집합

https://www.acmicpc.net/problem/2185


$O(N*\lg {NM})$ // 좌표압축을 하면 O(NlgN)으로 고칠 수 있다.

둘레 중 y축에 평행한 선분들 길이 합만 먼저 구해보자.
사각형 선분들 중 y축에 평행한 선분들만 저장한다.
이 선분들을 가지고 plane sweeping을 하면서 달라지는 길이만큼을 결과 변수에 누적한다.
주어진 사각형의 x,y좌표를 바꾸어 마찬가지로 누적하면 원래 사각형의 x축에 평행한 선분의 길이합도 구할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 5e3, MAX_L = 2e4;
struct st {
    int x, d, u, t;
    bool operator<(st i) const {
        return x < i.x || x == i.x&&t > i.t;
    }
}l[MAX_N * 2];
int n, res, p[MAX_N][4], t[MAX_L * 4], cnt[MAX_L * 4];
void query(int h, int l, int r, int gl, int gr, int k) {
    if (r<gl || gr<l) return;
    if (gl <= l && r <= gr) cnt[h] += k;
    else query(h * 2 + 1, l, (l + r) / 2, gl, gr, k),
        query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, k);
    if (cnt[h]) t[h] = r - l + 1;
    else t[h] = l == r ? 0 : t[h * 2 + 1] + t[h * 2 + 2];
}
void sw() {
    for (int i = 0; i < n; i++) {
        l[i] = { p[i][0],p[i][1],p[i][3],1 };
        l[i + n] = { p[i][2],p[i][1],p[i][3],-1 };
    }
    sort(l, l + 2 * n);
    for (int i = 0, tmp = 0; i < 2 * n; i++) {
        query(0, 0, MAX_L - 1, l[i].d, l[i].u - 1, l[i].t);
        res += abs(t[0] - tmp);
        tmp = t[0];
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) scanf("%d", &p[i][j]), p[i][j] += 1e4;
        if (p[i][0]>p[i][2]) swap(p[i][0], p[i][2]);
        if (p[i][1]>p[i][3]) swap(p[i][1], p[i][3]);
    }
    sw();
    for (int i = 0; i < n; i++) swap(p[i][0], p[i][1]), swap(p[i][2], p[i][3]);
    sw();
    printf("%d", res);
    return 0;
}

2261번: 가장 가까운 두 점

https://www.acmicpc.net/problem/2261

#include<stdio.h>
#include<algorithm>
#include<set>
#define x first
#define y second
using namespace std;
pair<int, int> p[100000];
set<pair<int, int> > st;
int n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &p[i].x, &p[i].y);
    sort(p, p + n);
    int res = 1e9, rt = sqrt(res);
    for (int i = 0, h = 0; i < n; i++) {
        while (p[i].x - p[h].x>rt) st.erase({ p[h].y, p[h++].x });
        for (set<pair<int, int> >::iterator it = st.lower_bound({ p[i].y - rt, -1e9 });
        it != st.end() && it->x <= p[i].y + rt; it++) {
            int d = (p[i].x - it->y)*(p[i].x - it->y) + (p[i].y - it->x)*(p[i].y - it->x);
            if (d < res) {
                res = d;
                rt = sqrt(d);
            }
        }
        st.insert({ p[i].y, p[i].x });
    }
    printf("%d", res);
    return 0;
}