[BOJ] 22238 - 가희와 btd5

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

BOJ - 가희와 btd5

문제 유형: 수학, 기하학, 정렬, 구현, 시뮬레이션

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 512MB

 

문제

btd5에는 Darting Gun Tower가 있습니다. Darting Gun Tower는 아래의 알고리즘으로 풍선을 공격합니다.

• 공격하고자 하는 목표물의 방향으로 공격 방향을 바꿉니다.
• 공격 방향에 있는 풍선들의 체력을 d씩 낮춥니다.

Darting Gun Tower는 좌표 (0, 0)에 하나 있습니다.
Darting Gun Tower가 공격을 하게 되면, 공격하는 방향에 놓인 모든 풍선들은 동일한 수치의 피해를 입히게 됩니다.
초기에 풍선은 N개 있고, Darting Gun Tower는 공격을 M번 하였습니다. 공격을 끝낼 때 마다, 남은 풍선의 수를 세어 주세요.
초기 상태에 Darting Gun Tower가 특정 방향으로 데미지가 109 이상의 공격을 했을 때, 모든 풍선을 제거할 수 있는 방법이 존재합니다.

 

입력

첫 번째 줄에 N, M이 주어집니다.

2번째 줄부터 N+1번째 줄까지 풍선이 있는 x좌표, y좌표, 체력이 주어집니다.

N+2번째 줄부터 N+M+1번째 줄까지 Darting Gun Tower의 공격 방향 (x, y)와, Darting Gun Tower가 준 데미지 d가 주어집니다.

 

출력

x번째 줄에 x번째 공격이 끝났을 때 남은 풍선의 개수를 출력해 주세요.

 

풀이

모두 한 직선 위에 있으므로, 유효한 기울기가 왔을때에만 데미지를 처리해서 남은 수를 이진탐색으로 빠르게 처리해주면 된다.

부동소수점 오차에 의해서, 실제로 나누지 말고 약분된 비율로 따진다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

pll normalize(ll x, ll y) {
    if (x == 0 && y == 0) return {0, 0};
    ll g = gcd(llabs(x), llabs(y));
    x /= g;
    y /= g;
    return {x, y};
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    pll main_dir = {0, 0};
    ll dmg = 0;

    vector<ll> nums;

    for (int i = 0; i < n; i++) {
        ll x, y, d;
        cin >> x >> y >> d;

        auto dir = normalize(x, y);
        if (main_dir.first == 0 && main_dir.second == 0) main_dir = dir;
        nums.emplace_back(d);
    }
    sort(nums.begin(), nums.end());

    int last_ans = nums.size();
    for (int i = 0; i < m; i++) {
        ll x, y, d;
        cin >> x >> y >> d;

        auto dir = normalize(x, y);
        if (dir != main_dir) {
            cout << last_ans << "\n";
            continue;
        }

        dmg += d;
        int ub = upper_bound(nums.begin(), nums.end(), dmg) - nums.begin();
        cout << nums.size() - ub << "\n";
        last_ans = nums.size() - ub;
    }

    return 0;
}