G. Blocked Billboard II

Editor: 김정현 (powergee)

PreviousF. Taming the Herd NextH. Lifeguards (Bronze)

Last updated 5 years ago

Was this helpful?

G. Blocked Billboard II

Editor: 김정현 (powergee)

문제 상황 설명

소 사료 광고판이 잔디깎이 광고판의 일부를 가리고 있는 상황에서, Bessie는 직사각형 모양의 가림막 하나로 잔디깎이 광고판을 모두 가리고자 합니다. 이때 필요한 가림막의 최소 넓이를 계산해야 합니다.

문제 풀이

여기서 중요한 점은, 소 사료 광고판이 이미 가리고 있는 부분은 또 가릴 필요가 없으나, 가림막을 단 하나만 사용할 수 있기 때문에, 문제의 풀이는 잔디깎이 광고판의 직사각형 모양 일부만 가려도 되는 경우와, 잔디깎이 광고판 전체를 가려야 하는 경우로 나뉩니다. 아래 그림으로 설명하겠습니다.

위 그림의 4가지 경우는 각각 소 사료 광고판이 잔디깎이 광고판의 우측, 좌측, 위, 아래 부분을 가린 경우입니다. 여기서 중요한 점은 네 경우 모두 소 사료 광고판이 잔디깎이 광고판을 두개의 직사각형으로 분할하고 있다는 점입니다. 이러한 상황에서는 소 사료 광고판이 가리지 않은 잔디깎이 광고판의 부분 넓이만 가리는 것이 가능합니다. 그리고 그러한 상황일 때의 정답 또한 아래와 같아짐은 자명합니다.

잔디깎이 광고판의 넓이 - (잔디깎이 광고판과 소 사료 광고판의 공통 넓이)

그렇다면 위의 4가지 경우가 아닌 경우 즉, 하나의 직사각형으로 잔디깎이 광고판 전체를 가려야 하는 경우는 어떤 경우일까요? 이 또한 아래 그림으로 확인하겠습니다.

광고판 전체를 가려야 하는 경우는 이전에 살펴본 4가지 경우를 제외한 전체입니다. 이들의 공통점은 소 사료 광고판이 잔디깎이 광고판을 두 직사각형으로 분할하지 않거나, 전혀 가리지 않는 경우입니다. 이러한 상황에서는 잔디깎이 광고판 전체를 가려야 하므로 정답 또한 그것의 전체 넓이와 같습니다.

이렇듯, 잔디깎이 광고판의 일부만 가려도 되는 경우(첫번째 그림)와 전체를 가려야 하는 경우(두번째 그림)는 정답을 계산하는 방법에 차이를 보입니다. 그렇기에 우리가 구현하는 알고리즘도 입력 상황이 둘 중 어느 상황에 해당하는지를 판별할 필요가 있습니다. 이들을 구별하기 위해선 어떻게 해야 할까요?

첫번째 그림에 해당하는 경우를 "첫번째 경우", 두번째 그림에 해당하는 경우를 "두번째 경우"라고 하겠습니다.

첫번째 경우에서 잔디깎이의 x 축 구간을 두 개로 나누는 경우(첫번째 그림의 위 2개 경우)는 아래 조건이 성립할 때와 같습니다.

비슷하게, 두번째 경우에서 잔디깎이의 y 축 구간을 두 개로 나누는 경우(첫번째 그림의 아래 2개 경우)는 아래 조건이 성립할 때와 같습니다.

그러므로 아래 조건이 성립하면 첫번째 경우이고, 성립하지 않으면 두번째 경우입니다.

지금까지 알아본 것이 문제를 해결하는 주요한 단서가 됩니다. 이를 토대로 예제 상황을 해석하면 아래와 같습니다.

예제의 상황은 소 사료 광고판이 잔디깎이 광고판을 두개의 직사각형으로 분할하지 않기 때문에, 잔디깎이 광고판의 전체를 가려야 합니다. 그렇기에 정답은 잔디깎이 광고판의 전체 넓이인 15 입니다.

정답 소스 (C++)

Blocked Billboard 2.cpp

#include <iostream>

typedef std::pair<int, int> Point;
typedef std::pair<int, int> Range;

int GetCommonRange(const Range& r1, const Range& r2)
{
    if (r1.second < r2.first || r2.second < r1.first)
        return 0;
    else if (r1.first <= r2.first && r2.first <= r1.second && r1.second <= r2.second)
        return r1.second - r2.first;
    else if (r2.first <= r1.first && r1.first <= r2.second && r2.second <= r1.second)
        return r2.second - r1.first;
    else if (r2.first <= r1.first && r1.second <= r2.second)
        return r1.second - r1.first;
    else if (r1.first <= r2.first && r2.second <= r1.second)
        return r2.second - r2.first;

    return 0;
}

class Rect
{
public:
    Point leftBottom;
    Point rightTop;

    Rect(const Point left, const Point right) : leftBottom(left), rightTop(right) {}

    int GetIntersection(const Rect& r) const
    {
        int xLength = GetCommonRange(Range(leftBottom.first, rightTop.first), Range(r.leftBottom.first, r.rightTop.first));
        int yLength = GetCommonRange(Range(leftBottom.second, rightTop.second), Range(r.leftBottom.second, r.rightTop.second));

        return xLength * yLength;
    }

    int GetArea()
    {
        return (rightTop.first - leftBottom.first) * (rightTop.second - leftBottom.second);
    }

    bool IsCovering(const Rect& r)
    {
        return  (leftBottom.second <= r.leftBottom.second && r.rightTop.second <= rightTop.second && !(r.leftBottom.first <= leftBottom.first && rightTop.first <= r.rightTop.first)) ||
                (leftBottom.first <= r.leftBottom.first && r.rightTop.first <= rightTop.first && !(r.leftBottom.second <= leftBottom.second && rightTop.second <= r.rightTop.second));
    }
};

int main()
{
    int x1, y1, x2, y2;

    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    Rect lawn({x1, y1}, {x2, y2});

    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    Rect feed({x1, y1}, {x2, y2});

    if (feed.IsCovering(lawn))
        printf("%d", lawn.GetArea() - lawn.GetIntersection(feed));
    else printf("%d", lawn.GetArea());

    return 0;
}