[BOJ] 14616 - Explore Space

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

BOJ - Explore Space

문제 유형: 기하학, 수학, 정렬, 스위핑

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 256MB

 

문제

지금으로부터 멀지 않은 미래 항성 간 이동이 가능해진 인류는 새로운 보금자리를 찾기 위한 여정을 떠난다. 긴 시간 끝에 마지막 웜홀을 눈앞에 두고 있지만 웜홀 안에는 방사능 층이 가득해 그냥 이용할 경우 수많은 사람들이 피폭당할 수 있다.

다행히 인류에게는 방사능 층을 파괴할 수 있는 레이저를 가지고 있다. 레이저는 발사 위치로부터 반직선 형태로 발사되며 충돌하는 모든 방사능 층을 파괴할 수 있는 능력을 가지고 있다. 웜홀 안에 존재하는 방사능 층의 상태와 레이저의 발사 위치들이 주어졌을 때 레이저를 발사한 뒤 남은 방사능 층이 몇 개인지 시뮬레이션 하는 프로그램을 작성해보자.

편의상 레이저의 위치는 (0, 0)이라고 하자. 이때 방사능 층들의 위치는 2차원 좌표 평면상 제1사분면의 선분으로 표현할 수 있다. 레이저의 발사 위치는 (X,Y)로 나타낼 수 있으며 이는 (0, 0)에서 (X,Y)로 향하는 반직선 형태로 레이저를 발사함을 의미한다.

다음 그림은 한 방사능 층에 대해 레이저를 발사하는 서로 다른 두 경우를 보여준다.

그림 (a)는 (2, 4)를 향해 발사한 레이저가 방사능 층과 충돌해 방사능 층을 파괴하는 모습을 나타낸다. 그림 (b)는 (3, 2)를 향해 발사한 레이저가 방사능 층을 파괴하지 못하고 빗겨나가는 모습을 나타낸다.

발사된 레이저가 방사능 층 선분의 시작 혹은 끝을 정확히 지나도 방사능 층과 레이저가 충돌한다고 간주한다. 발사된 레이저의 두께는 정말 얇기 때문에 레이저의 두께를 고려해서 계산할 필요는 없다.

 

입력

첫 번째 줄에 웜홀 안에 존재하는 방사능 층의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에 걸쳐 i(1 ≤ i ≤ N)번째 방사능 층을 나타내는 선분의 양끝점 좌표가 주어진다. 다음 줄에는 레이저의 발사 횟수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 걸쳐 j(1 ≤ j ≤ M)번째 레이저의 발사 위치가 주어진다. 입력으로 주어지는 모든 좌표의 크기는 1보다 크거나 같고 100,000보다 작거나 같다. 방사능 층을 나타내는 선분의 시작과 끝은 동일할 수 있다.

 

출력

첫 번째 줄에 모든 레이저를 발사한 뒤 웜홀 안에 존재하는 방사능 층의 개수를 출력한다

 

풀이

각각 최대 10^5의 크기이기에, n log n의 시간이 필요하다.

(0, 0)에서 레이저가 발사되기에, 발사되는 레이저는 y절편 없이 y = ax꼴의 반직션의 기울기로 표현될 수 있다.

모든 레이저들을 기울기로 표현하고, 오름차순 정렬해준다.

그 뒤, 각각의 방사능 층 역시, 두 양끝점이 각도의 최대 및 최소 값이 된다.

 

두 최대 및 최소 기울기 범위에 레이저가 하나라도 있으면, 그 방사능 층은 삭제된다.

부동소수점 계산의 오류를 없애기 위해, 기울기를 두 기약분수의 분자와 분모로 표현가능하고, 수의 비교는 통분을 하여 비교하는 식으로 해주면 된다.

 

방사능 층의 양끝점이 같은 엣지케이스도 있으니, 유의해야 한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

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

void normalize(int &a, int &b) {
    int GCD = gcd(a, b);
    a /= GCD;
    b /= GCD;
}

auto comp = [](const array<int, 2> &a, const array<int, 2> &b) -> bool {
    return (long long)a[0] * b[1] < (long long)b[0] * a[1];
};

int main(int argc, char *argv[]) {
    int n;
    cin >> n;
    vector<array<array<int, 2>, 2>> segments(n);
    vector<bool> isAlive(n, true);
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        normalize(x1, y1);
        normalize(x2, y2);
        array<int, 2> pointA = {x1, y1};
        array<int, 2> pointB = {x2, y2};
        if (comp(pointA, pointB)) {
            segments[i][0] = pointA;
            segments[i][1] = pointB;
        } else {
            segments[i][1] = pointA;
            segments[i][0] = pointB;
        }
    }

    int m;
    cin >> m;
    vector<array<int, 2>> lasers(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        normalize(a, b);
        lasers[i] = {a, b};
    }
    sort(lasers.begin(), lasers.end(), comp);

    int ans = n;
    for (int i = 0; i < n; i++) {
        auto &a = segments[i][0];
        auto &b = segments[i][1];

        if (a[0] == b[0] && a[1] == b[1]) {
            int idx = lower_bound(lasers.begin(), lasers.end(), a, comp) -
                      lasers.begin();
            if (idx < m && lasers[idx][0] == a[0] && lasers[idx][1] == b[1]) {
                ans--;
                continue;
            }
        }

        int idx1 =
            lower_bound(lasers.begin(), lasers.end(), a, comp) - lasers.begin();
        int idx2 =
            upper_bound(lasers.begin(), lasers.end(), b, comp) - lasers.begin();
        if (idx1 < idx2) {
            ans--;
        }
    }

    cout << ans << "\n";

    return 0;
}