원자 수는 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까지 빠른 타이밍부터 돌면서 충돌검사를 해준다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #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; } | cs |
'SWEA' 카테고리의 다른 글
| 핀볼 런타임 에러나는 TC (0) | 2018.10.07 |
|---|---|
| 5644. 무선 충전 (0) | 2018.09.27 |
| 5658. 보물상자 비밀번호 (0) | 2018.09.21 |
| 5656. 벽돌 깨기 (0) | 2018.09.21 |
| 5653. 줄기세포 배양 (4) | 2018.09.21 |