[BOJ/Platinum 3] 백준 27656 양궁(C++)

문제 링크

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

 

문제

평면 위에 N개의 점이 있다. 남은 점이 없을 때까지 다음 시행을 반복하여 과녁을 만든다.

• 남은 점들을 모두 포함하는 가장 작은 볼록 다각형을 얻는다.
• 볼록 다각형 경계에 있는 점들을 제거한다.

한 점이 남거나 남은 점들이 한 직선 위에 있는 경우는 없다. 또한, 볼록 다각형 경계에 있는 어느 세 점도 한 직선 위에 있지 않음이 보장된다.

얻은 도형을 순서대로 P1, P2, ⋯, Pk라 할 때, 화살의 점수는 화살이 꽂힌 위치가 P1 외부이면 0, P1 내부이면서 P2 외부이면 1, ⋯, Pk−1 내부이면서 Pk 외부이면 k−1, Pk 내부이면 k이다. 도형의 내부는 경계를 포함한다.

 Q번 화살을 쏠 때, 각각의 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N이 주어진다. (3 ≤ N ≤ 1,000)

둘째 줄부터 N개의 줄에 걸쳐 각 점의 좌표를 나타내는 −10^9 이상 10^9 이하의 두 정수가 공백을 사이에 두고 주어진다.

그다음 줄에 화살을 쏘는 횟수 Q가 주어진다. (1 ≤ Q ≤ 1,000,000)

그다음 줄부터 Q개의 줄에 걸쳐 화살이 꽂힌 위치의 좌표를 나타내는 −10^9 이상 10^9 이하의 두 정수가 공백을 사이에 두고 주어진다.

출력

화살의 점수를 한 줄에 하나씩 출력한다.

예제 입력 1

11
4 4
-4 -4
0 1
1 -1
4 -4
0 -3
-4 4
-2 0
0 3
-3 0
3 0
7
4 5
-4 2
-2 3
1 2
1 0
-1 0
0 0

예제 출력 1

0
1
1
2
2
3
3

알고리즘 분류

• 이분 탐색
• 그레이엄 스캔
• 볼록 다각형 내부의 점 판정

풀이

우선 남은 점들을 모두 포함하는 볼록 다각형을 그레이엄 스캔을 통해 더 이상 점이 남지 않을 때까지 찾는다.

한 점이 남거나, 남은 점들이 한 직선 위에 있는 경우는 없기 때문에 모든 점이 볼록 다각형의 꼭짓점이 된다.

또한 볼록 다각형 경계에 어떠한 점도 존재하지 않기 때문에, 외적의 결과가 0이 되는 경우도 없다.

우선 점의 X, Y좌표의 절댓값은 10^9가 최대이므로 2*10^9를 절댓값으로 갖는 좌표 4개를 꼭짓점으로 갖는 볼록 다각형을 0번째 과녁이라고 하자.

그리고 그레이엄 스캔을 여러 번 반복해서 볼록 다각형 형태의 과녁을 계속해서 만들어나가며, 사용한 점은 제거한다.

마지막으로 Q번의 화살을 쐈을 때, 화살이 어떤 과녁에 적중하는지 볼록 다각형 내부의 점을 판정하는 알고리즘을 통해 찾는다.

우선 특정 볼록 다각형의 꼭짓점들을 반시계 방향으로 정렬했을 때 첫 번째 벡터(첫 번째 꼭짓점 - 두 번째 꼭짓점)와 (두 번째 꼭짓점 - 화살의 위치)를 외적 계산했을 때 0보다 작다면 우회전을 이루는 것이므로, 볼록 다각형 바깥에 위치한다고 할 수 있다. 또한 마지막 벡터(첫 번째 꼭짓점 - 마지막 꼭짓점)와 (마지막 꼭짓점 - 화살의 위치)를 외적 계산했을 때 0보다 크다면 좌회전을 이루는 것이므로, 마찬가지로 볼록 다각형 바깥에 위치한다고 할 수 있다. 이런 경우에는 해당 과녁 바깥에 있다고 판정한다.

두 경우에 해당하지 않는다면, 이분 탐색을 통해 마지막으로 비교할 두 점을 찾고, 각각의 점과 화살이 이루는 벡터 2개를 외적 계산했을 때 좌회전을 이룬다면 볼록 다각형 바깥에 있는 것으로 판정한다. 여기서는 경계에 위치해도 과녁 안쪽에 있는 것으로 판정되기 때문에, 외적의 결과가 0이어도 볼록 다각형 안쪽에 있다고 판정하였다.

처음에는 모든 벡터를 가지고 일일히 외적 계산을 했지만, 이것 때문에 시간 초과가 발생한다고 판단하여 점이 내부에 있는지를 판정하는 다른 알고리즘을 조사하였고, 이분 탐색을 통해 시간을 단축시킬 수 있다는 것을 알아내었다.

아무튼 이 방법을 통해 해당 과녁 안쪽에 화살이 위치하는지를 찾는다. 여기서 또 이분 탐색을 통하여 현재 과녁 바깥에 화살이 위치했다면 범위의 끝을 현재 과녁의 번호 - 1로 변경하고, 현재 과녁 안쪽에 화살이 위치했다면 범위의 시작을 현재 과녁의 번호 + 1로 변경하면서 탐색해주었다.

볼록 껍질을 응용한 매우 재미있는 문제이니 풀어보시길 바란다. 보니까 다른 형님들은 다 1~3번만에 푸셨는데 본인만 16회의 시도 끝에 풀었다..

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MAX 1001
#define INF 2e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct POINT {
    LL X, Y;
};

LL N, Q, X, Y, MinX, MinY, First, Low, High, Mid;
vector<POINT> Point;
vector<POINT> CV;
vector<POINT> P[MAX];
int PCount = 1;
bool Flag = true;

void init() {
    MinX = INF;
    MinY = INF;
    CV.clear();
}

LL distance(POINT A, POINT B) {
    return (A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y);
}

LL CCW(POINT A, POINT B, POINT C) {
    LL OP = ((A.X * B.Y) + (B.X * C.Y) + (C.X * A.Y));
    OP -= ((A.Y * B.X) + (B.Y * C.X) + (C.Y * A.X));
    return OP;
}

bool Comp(POINT A, POINT B) {
    LL NowCCW = CCW(Point[0], A, B);
    if (NowCCW != 0) {
        return (NowCCW > 0);
    }
    if (A.X != B.X) {
        return (A.X < B.X);
    }
    return (A.Y < B.Y);
}

void graham_Scan() {
    if (Point.size() <= 2) {
        Flag = false;
        return;
    }
    for (int i = 0; i < Point.size(); i++) {
        if ((MinX > Point[i].X) || ((MinX == Point[i].X) && (MinY > Point[i].Y))) {
            MinX = Point[i].X;
            MinY = Point[i].Y;
            First = i;
        }
    }
    swap(Point[0], Point[First]);
    sort(Point.begin() + 1, Point.end(), Comp);
    for (int i = 0; i < Point.size(); i++) {
        while ((CV.size() >= 2) && (CCW(Point[i], CV[CV.size() - 2], CV[CV.size() - 1]) < 0)) {
            CV.pop_back();
        };
        CV.push_back(Point[i]);
    }
    if (CV.size() <= 2) {
        Flag = false;
        return;
    }
    for (int i = 0; i < CV.size(); i++) {
        for (int j = 0; j < Point.size(); j++) {
            if ((Point[j].X == CV[i].X) && (Point[j].Y == CV[i].Y)) {
                Point.erase(Point.begin() + j);
                P[PCount].push_back(CV[i]);
                break;
            }
        }
    }
}

void settings() {
    P[0].push_back({ (LL)-INF,(LL)-INF });
    P[0].push_back({ (LL)INF,(LL)-INF });
    P[0].push_back({ (LL)INF,(LL)INF });
    P[0].push_back({ (LL)-INF,(LL)INF });
    while (1) {
        init();
        graham_Scan();
        if (!Flag) {
            break;
        }
        PCount++;
    };
}

bool isInner(LL PX, LL PY, int Now) {
    POINT NowP;
    NowP.X = X;
    NowP.Y = Y;
    LL NowCCW = CCW(P[Now][0], P[Now][1], NowP);
    if (NowCCW < 0) {
        return false;
    }
    NowCCW = CCW(P[Now][0], P[Now][(int)P[Now].size() - 1], NowP);
    if (NowCCW > 0) {
        return false;
    }

    int Left = 1;
    int Right = (int)P[Now].size() - 1;
    while (Left + 1 < Right) {
        int Middle = (Left + Right) / 2;
        if (CCW(P[Now][0], P[Now][Middle], NowP) >= 0) {
            Left = Middle;
        }
        else {
            Right = Middle;
        }
    };

    return (CCW(P[Now][Left], NowP, P[Now][Right]) <= 0);
}

void find_Answer(LL PX, LL PY) {
    int Answer = 0;
    Low = 0;
    High = PCount - 1;
    while (Low <= High) {
        Mid = (Low + High) / 2;
        if (isInner(PX, PY, Mid)) {
            Answer = Mid;
            Low = Mid + 1;
        }
        else {
            High = Mid - 1;
        }
    };
    cout << Answer << "\n";
}

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> X >> Y;
        POINT Tmp;
        Tmp.X = X;
        Tmp.Y = Y;
        Point.push_back(Tmp);
    }
    settings();
    cin >> Q;
    while (Q--) {
        cin >> X >> Y;
        find_Answer(X, Y);
    };
}

int main() {
    FASTIO
    input();

    return 0;
}