스터디 23/01/14 22238 : 가희와 btd5

22238번: 가희와 btd5 (acmicpc.net)

22238번: 가희와 btd5

풀이
1. 공격은 직선으로 나간다.
2. 공격과 같은 직선상에 있는 풍선들만 공격받는다.
3. 같은 직선인지 판단하는 방법은 기울기를 이용한다.

4. 기울기를 표현할 때는 실수연산이 아닌 최대공약수와 pair를 이용해 표현, 실수형에선 오차가 발생할 수 있음
     최대공약수를 구할 때 좌표중 음수가 있을 경우 음수를 절대값 처리를 해줘야함
5. 데미지를 모든 풍선들에 적용시키기엔 시간이 오래걸리기 때문에 누적된 데미지를 이용해
    이분탐색, 우선순위큐 등을 이용해 구현(본인은 우선순위 큐 사용)

 

문제포인트
초기상태에 첫 공격으로 모든 풍선을 제거할 수 있음 = 풍선은 일직선상으로만 주어짐
풍선과 공격이 일직선상으로 일치할때만 공격하면됨

 

시간복잡도

N = 풍선의 개수 = 2 * 1e5
M = 공격 횟수 = 2 * 1e5
1) 풍선을 heap에 삽입 : n logn 
2) 공격당한 풍선 pop : m + n logn

 

#include<bits/stdc++.h>
#include<time.h>


#define MAX 5000001
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

struct Balloon {
    priority_queue<ll, vector<ll>, greater<ll>> hp;
    ll damage = 0;
};

Balloon myBalloon;
void shoot(ll x, ll y, ll d, pll balloonInc) {
    ll g = gcd(abs(x), abs(y));
    pll atackInc = { x / g, y / g };

    if (atackInc != balloonInc)
        return;

    myBalloon.damage += d;
    priority_queue<ll, vector<ll>, greater<ll>>& myHeap = myBalloon.hp;
    ll &myDM = myBalloon.damage;
    while (!myHeap.empty() && myHeap.top() <= myDM) {
        myHeap.pop();
    }
}
int main() {
    init();
    int n, m; cin >> n >> m;
    pll incline;
    for (int i = 0; i < n; i++) {
        ll x, y, h; cin >> x >> y >> h;
        ll g = gcd(abs(x), abs(y));
        incline = { x / g, y / g };

        myBalloon.hp.push(h);
    }
    for (int i = 0; i < m; i++) {
        ll x, y, d; cin >> x >> y >> d;
        shoot(x, y, d, incline);
        cout << myBalloon.hp.size() << "\n";
    }
}