백준 6818 - Wireless (C++)

문제 정보

• https://www.acmicpc.net/problem/6818
• 스위핑, 기하학

---

문제 정리

2차원 좌표평면에 K개의 무선장치가 달려 있으며, 각 무선 장치는 반지름이 R_i인 원 형태의 범위에 B_i의 세기로 신호를 쏴준다.
Bob은 한 번에 여러 신호를 수신할 수 있으며 각각의 신호의 세기는 더할 수 있을 때, Bob이 수신할 수 있는 신호의 최대 세기를 구하고, 그러한 정수 좌표의 개수를 구하는 문제이다.

이 그림은 예제 1의 그림이며, 신호 세기가 12인 곳을 표시한 것이다.

---

풀이

얼마전에 푼 #3552번이 생각났다.
모든 정수 좌표에 대해 원과의 교점을 구하고 그 점에서의 신호 세기를 구하면 O(NMK)로 TLE가 발생한다. 따라서, 스위핑으로 x축을 훑으며 원과의 교점을 빠르게 구하자.

1. 각 x에 대해 2~3번 과정을 반복해준다.
2. 현재 x좌표가 a일 때, 모든 원에 대해 x=a와 겹치는 y구간을 구한다.
   • 신호 세기의 최대값을 구해야 하므로 차분 배열 트릭을 이용해 각 원별로 신호의 세기를 차분 배열에 저장했다.
   • 만약 신호의 세기가 b이고 구간 [c, d]가 원과 겹치는 y구간이라면, diff[c] += b, diff[d+1] -= b를 하는 방식으로 처리해준다.
3. 각 x에서 얻은 (최대 세기, 그 개수)를 전역 답과 비교해 갱신한다.
   • 더 큰 최대값이면 값을 바꾸고 개수도 교체한다.
   • 최대값이 같으면 개수만 누적한다.

---

후기

C++ 연습 겸 C++23으로 풀었다. 앞으로도 웬만한 문제는 C++로 풀듯?
아직 덜 익숙해서 그런가 디버깅이 꽤 힘들었다.

---

코드

// 백준 6818

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

struct Circle {
    int x, y, r, bitrate;
};

vector<Circle> circles;


// 원 C가 x=a와의 정수 교점 범위 반환
pair<int, int> cross(Circle c, int a) {
    double dist = sqrt(c.r*c.r-(c.x-a)*(c.x-a));
    return {(int)ceil(c.y-dist), (int)(c.y+dist)};
}


pair<int, int> solve(int X, int Y, int K) {
    int maxBitrate = 0;
    int maxCount = 0;
    vector<int> diff(Y+2, 0);

    for (int x=1; x<=X; x++) {
        fill(diff.begin(), diff.end(), 0);

        // 모든 원에 대해 포함 범위 계산
        for (const Circle& c : circles) {
            if (x < c.x-c.r || x > c.x+c.r) continue;

            // 원의 포함 범위를 차분 배열에 저장
            auto [startY, endY] = cross(c, x);
            startY = max(1, startY);
            endY = min(Y, endY);
            diff[startY] += c.bitrate;
            if (endY < Y) {
                diff[endY+1] -= c.bitrate;
            }
        }

        // 차분 배열에서 최대값 추출
        int accSum = 0;
        int totalCount = 0;
        int diffMax = 0;
        for (int i=1; i<=Y; i++) {
            accSum += diff[i];
            if (diffMax < accSum) {
                totalCount = 1;
                diffMax = accSum;
            }
            else if (diffMax == accSum)
                totalCount += 1;
        }

        // 이전 x좌표에서의 최대값과 비교 및 갱신
        if (maxBitrate < diffMax) {
            maxCount = totalCount;
            maxBitrate = diffMax;
        }
        else if (maxBitrate == diffMax)
            maxCount += totalCount;
    }

    return {maxBitrate, maxCount};
}


int main() {
    cin.tie(0);
	ios_base::sync_with_stdio(0);

    int X, Y, K;
    cin >> Y >> X >> K;
    circles.resize(K);

    for (int i=0; i<K; i++)
        cin >> circles[i].x >> circles[i].y >> circles[i].r >> circles[i].bitrate;

    pair<int, int> result = solve(X, Y, K);
    cout << result.first << '\n' << result.second << '\n';
}