[Algorithms] [BOJ 3121] 빨간 점, 파란 점

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

그 테크닉을 배웠다. (2022.1.5 추가: rotating sweep line 이라고 부르는 것 같다.)

 

$N$개의 점이 있을 때, 특정 기울기의 법선 벡터를 가지는 직선에 점들을 정사영하여 그 순서를 알고 싶다. 만약 Naive하게 구현한다면 각도는 최대 $O(N^2)$개, 점들의 정렬에 대략 $O(Nlog{N})$이 소요될 것이므로 시간이 너무 오래 걸린다.

하지만 잘 생각해보면 정렬된 상태는 법선벡터와 어떤 두 점을 잇는 직선의 기울기가 동일해질 때 그 두 점의 위치만 인접한 상태에서 바뀌기 때문에, 점 쌍들을 기울기로 정렬하여 순서대로 두 점의 위치만 바꾸어주면 모든 $N^2$개의 각도에서 정사영한 순서를 알 수 있다. 각도 정렬에 $O(N^2log{N})$이 소요되며 시간복잡도도 이와 같게 된다.

 

처음에는 코딩을 더럽게 했지만 oj.uz에서 갓들의 코드를 참고하며 깔끔하게 고쳤다. 초기 상태를 법선벡터가 -y방향에서 미세하게 반시계 방향으로 틀어진 상태로 놓고 각 점쌍들(스왑하는 이벤트들)의 기울기를 x변화량이 양수가 되도록 저장하여 법선벡터가 1, 4사분면만 돌도록 하면 깔끔하게 코딩할 수 있다.

 

참고로 불도저, KOI2019 고압선도 비슷하게 풀면 된다. 또 이 문제와 다르게 세 점이 일직선에 있는 경우의 처리도 해야 하는데, 아래와 비슷한 구현을 하면 알아서 잘 처리가 되므로(코드를 잘 보면 알겠지만, 버블정렬에서 모든 swap이 일어나듯이 일직선에 있는 점들의 순서가 뒤집힌다.) 참고하시길

 

(2024.02.18 추가)

SUAPC에서 나온 문제에 따르면, (별로 쓸데없긴 하지만) set으로 기울기 후보들을 관리하여 메모리를 O(N)으로 줄일 수 있다.

 

코드

#include <bits/stdc++.h>
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 1010;
const int INF = 1e9;
const ll LINF = 9e18;

class SegmentTree {
    struct Node {
        int lmx = 0, rmx = 0, mx = 0;
        bool f = false;
        Node operator + (Node b) {
            Node ret;
            if(f) ret.lmx = lmx + b.lmx;
            else ret.lmx = lmx;
            if(b.f) ret.rmx = rmx + b.rmx;
            else ret.rmx = b.rmx;
            if(f && b.f) ret.f = true;
            ret.mx = max({mx, b.mx, rmx + b.lmx});
            return ret;
        }
    };
    vector <Node> tree;
    int sz;
public:

    void Init(int n) {
        tree.resize(4*n+10);
        sz = n;
    }

    void Update(int k, bool f) {
        update(1, 0, sz-1, k, f);
    }
    void update(int node, int s, int e, int k, bool f) {
        if(s == e) {
            if(f) tree[node].f = true, tree[node].lmx = tree[node].rmx = tree[node].mx = 1;
            else tree[node].f = false, tree[node].lmx = tree[node].rmx = tree[node].mx = 0;
            return;
        }
        int m = s + e >> 1;
        if(k <= m) update(node<<1, s, m, k, f);
        else update(node<<1|1, m+1, e, k, f);
        tree[node] = tree[node<<1] + tree[node<<1|1];
    }

    int get() {
        return tree[1].mx;
    }
};

struct Point {
    int x, y;
    bool c = false;
    bool operator < (const Point &p) const {
        return pii(x, y) < pii(p.x, p.y);
    }
};

struct Evt{
    int dx, dy, idx1, idx2;
    Evt(int dx, int dy, int idx1, int idx2) : dx(dx), dy(dy), idx1(idx1), idx2(idx2) {}
    bool operator < (const Evt &s)const{
    	ll k = 1LL * dx * s.dy - 1LL * dy * s.dx;
        if(k != 0) return k > 0;
        return pii(idx1, idx2) < pii(s.idx1, s.idx2);
    }
};

ll ccw(Evt a, Evt b) {
    return (ll)a.dx * b.dy - (ll)b.dx * a.dy;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n;
    cin >> n;
    vector <Point> a(n);
    vector <int> pos(n);

    for(int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
        string s;
        cin >> s;
        if(s == "R") a[i].c = true;
    }

    if(n == 1) {
        if(a[0].c) cout << 1 << endl;
        else cout << 0 << endl;
        return 0;
    }
    sort(all(a));
    for(int i = 0; i < n; i++) {
        pos[i] = i;
    }

    vector <Evt> line;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            line.eb(a[j].x - a[i].x, a[j].y - a[i].y, i, j);
        }
    }
    sort(all(line));
    int idx = 0;
    SegmentTree ST;
    ST.Init(n);
    for(int i = 0; i < n; i++) {
        ST.Update(i, a[i].c);
    }

    int ans = ST.get();
    for(int i = 0; i < line.size(); i++) {
        int rx = pos[line[i].idx1], ry = pos[line[i].idx2];
        swap(a[rx], a[ry]);
        swap(pos[line[i].idx1], pos[line[i].idx2]);
        ST.Update(rx, a[rx].c);
        ST.Update(ry, a[ry].c);
        if(i + 1 < line.size() && ccw(line[i], line[i+1]) == 0) continue;
        ans = max(ans, ST.get());
    }
    cout << ans << endl;
}