5648. 원자 소멸 시뮬레이션

원자 수는 1000개, 방향은 상하좌우, 속도는 초당 1로 동일하다.

처음 위치가 -1000<=x,y<=1000 이므로 저 범위 내에서 다른 원자와 충돌하지 않으면 영원히 충돌하지 않는다.

1. i 0~N-1, j i+1~N-1을 돌면서 a[i]와 a[j]가 충돌하는지 검사하고 충돌한다면 충돌하는 타이밍을 t라고 할 때 q[t]에 {i,j} 형식으로 저장한다.

2. 직각으로 만나는 경우는 무조건 정수 타이밍에 충돌하기 때문에 상관없지만 상하 or 좌우 방향으로 서로를 향해 갈 때는 거리가 홀수면 타이밍이 .5가 나오므로 그냥 모든 시간에 *2를 해버린다.

3. 1~4002까지 빠른 타이밍부터 돌면서 충돌검사를 해준다.  

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
struct p {
    int x, y, w, c;
};
typedef pair<int, int> pii;
 
int d[1001];
p a[1001];
queue<pii> q[4040];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t, n;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        cin >> n;
        register int i, j;
 
        for (i = 0; i < n; ++i) {
            cin >> a[i].x >> a[i].y >> a[i].w >> a[i].c;
            d[i] = -1;
        }
 
        for (i = 0; i < n; ++i) {
            for (j = i + 1; j < n; ++j) {
                int ti = i;
                int tj = j;
                if (a[ti].w > a[tj].w) swap(ti, tj);
 
                if (a[ti].w == 0) {
                    if (a[tj].w == 1) {
                        if (a[ti].y < a[tj].y && a[ti].x == a[tj].x) {
                            q[a[tj].y - a[ti].y].push({ i,j });
                        }
                    }
                    else if (a[tj].w == 2) {
                        if (a[ti].x < a[tj].x && a[tj].y > a[ti].y &&
                            a[tj].y - a[ti].y == a[tj].x - a[ti].x) {
                            q[2 * (a[tj].y - a[ti].y)].push({ i,j });
                        }
                    }
                    else if (a[tj].w == 3) {
                        if (a[ti].x > a[tj].x && a[tj].y > a[ti].y &&
                            a[ti].x - a[tj].x == a[tj].y - a[ti].y) {
                            q[2 * (a[ti].x - a[tj].x)].push({ i,j });
                        }
                    }
                }
                else if (a[ti].w == 1) {
                    if (a[tj].w == 2) {
                        if (a[ti].x < a[tj].x && a[ti].y > a[tj].y &&
                            a[tj].x - a[ti].x == a[ti].y - a[tj].y) {
                            q[2 * (a[tj].x - a[ti].x)].push({ i,j });
                        }
                    }
                    else if (a[tj].w == 3) {
                        if (a[ti].x > a[tj].x && a[ti].y > a[tj].y &&
                            a[ti].x - a[tj].x == a[ti].y - a[tj].y) {
                            q[2 * (a[ti].x - a[tj].x)].push({ i,j });
                        }
                    }
                }
                else if (a[ti].w == 2) {
                    if (a[tj].w == 3) {
                        if (a[ti].x > a[tj].x && a[ti].y == a[tj].y) {
                            q[a[ti].x - a[tj].x].push({ i,j });
                        }
                    }
                }
            }
        }
 
        int ans = 0;
 
        for (i = 1; i < 4004; ++i) {
            while (q[i].size()) {
                int u = q[i].front().first;
                int v = q[i].front().second;
                q[i].pop();
                if (d[u] != -1 && d[v] != -1) continue;
                if (d[u] == i && d[v] == -1) {
                    d[v] = i;
                    ans += a[v].c;
                }
                else if (d[u] == -1 && d[v] == i) {
                    d[u] = i;
                    ans += a[u].c;
                }
                else if (d[u] == -1 && d[v] == -1) {
                    d[u] = d[v] = i;
                    ans += a[u].c + a[v].c;
                }
            }
        }
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}