백준 3878 점 분리 C++

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

이 문제도 볼록껍질 문제와 유사하다.

직선을 활용해서, 두 볼록껍질을 양분할 수 있는 지를 판단하는 문제이기 때문에, 예외 처리를 해줘야 한다.

한 볼록 껍질 도형에, 다른 볼록 껍질 도형이 들어가 있는 경우, 도형 교차 판별에서는 교차하지 않는다고 판단되기 때문에 추가적으로 처리 해줘야 한다.

이를 판단하는 방법은 다음과 같다.

특정 껍질을 감싸고 있는 큰 껍질(큰 볼록껍질)의 변들을 기준으로 작은 볼록 껍질의 점을 CCW하게 되면 모두 양수가 나온다.

이 때 외적은 교환 법칙이 성립하지 않기 때문에, CCW를 사용하는 순서와 방향이 중요하다.

반시계 방향으로 정렬해서 껍질을 만들었기 때문에, 검사도 반시계 방향으로 돌게 해주어야 한다.

따라서 스택에 있는 볼록 껍질을 이루는 점의 리스트를 벡터에 옮겨 올 때, 본래의 순서(반시계로 정렬된 순서)를 유지하면서 리스트에 들어갈 수 있게 정렬해줘야한다.

또한, CCW로 검사를 할 때에도, 점은 상관없지만 검사하는 선분은 반시게 방향으로 사용될 수 있도록 해야한다.

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
struct POS {
    double x, y;
}b[101], w[101];
int B, W;
stack<int> stk;
vector<int> bHull, wHull;
int ccw(POS p1, POS p2, POS p3) {
    long double ret = (p1.x*p2.y + p2.x*p3.y + p3.x*p1.y) - (p1.y*p2.x + p2.y*p3.x + p3.y * p1.x);
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0;
}
long double distSquare(POS p1, POS p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
bool cmpB(POS p1, POS p2) {
    if (ccw(b[0], p1, p2) > 0) return true;
    else if (ccw(b[0], p1, p2) < 0) return false;
    else {
        long double dist1 = distSquare(b[0], p1);
        long double dist2 = distSquare(b[0], p2);
        if (dist1 < dist2) return true;
        else return false;
    }
}
bool cmpW(POS p1, POS p2) {
    if (ccw(w[0], p1, p2) > 0) return true;
    else if (ccw(w[0], p1, p2) < 0) return false;
    else {
        long double dist1 = distSquare(w[0], p1);
        long double dist2 = distSquare(w[0], p2);
        if (dist1 < dist2) return true;
        else return false;
    }
}
void grahamScan(POS p[],int num, int flag) {
    
    stk.push(0);
    if (num > 1) //정점이 2개 이상인 경우에만 
        stk.push(1);
    int next = 2;
    
 
    while (next < num) {
        while (stk.size() >= 2) {
            int sec = stk.top();
            stk.pop();
            int fir = stk.top();
            if (ccw(p[fir], p[sec], p[next]) > 0) {
                stk.push(sec);
                break;
            }
        }
        stk.push(next++);
    }
 
    if (flag == 0) {
        while (!stk.empty()) {
            bHull.push_back(stk.top());
            stk.pop();
        }
        sort(bHull.begin(), bHull.end()); //스택에 뒤집어져서 들어가 있으니까 순서를 맞춰서 넣어줌
        bHull.push_back(bHull[0]);
    }
    else {
        while (!stk.empty()) {
            wHull.push_back(stk.top());
            stk.pop();
        }
        sort(wHull.begin(), wHull.end());
        wHull.push_back(wHull[0]);
    }
}
bool isCross(POS p1, POS p2, POS p3, POS p4) {
    if (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && 
        ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0) {
        
        if ((p1.x < p3.x && p1.x < p4.x && p2.x < p3.x && p2.x < p4.x) ||
            (p3.x < p1.x && p3.x < p2.x && p4.x < p1.x && p4.x < p2.x)) return false;
        if ((p1.y < p3.y && p1.y < p4.y && p2.y < p3.y && p2.y< p4.y) ||
            (p3.y < p1.y && p3.y < p2.y && p4.y < p1.y&& p4.y < p2.y)) return false;
        return true;
    }
    return false;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        bHull.clear();
        wHull.clear();
        cin >> B >> W;
        double bymin = 20000, wymin = 20000;
        int byminIdx = 0, wyminIdx = 0;
        for (int i = 0; i < B; i++) {
            cin >> b[i].x >> b[i].y;
            if (b[i].y < bymin) {
                bymin = b[i].y;
                byminIdx = i;
            }
            else if (b[i].y == bymin) {
                if (b[i].x < b[byminIdx].x) byminIdx = i;
            }
        }
        swap(b[0], b[byminIdx]);
        sort(b + 1, b + B, cmpB);
        grahamScan(b, B, 0); //역순으로 벡터 형성
        
        for (int i = 0; i < W; i++) {
            cin >> w[i].x >> w[i].y;
            if (w[i].y < wymin) {
                wymin = w[i].y;
                wyminIdx = i;
            }
            else if (w[i].y == wymin) {
                if (w[i].x < w[wyminIdx].x) wyminIdx = i;
            }
        }
        swap(w[0], w[wyminIdx]);
        sort(w + 1, w + W, cmpW);
        grahamScan(w, W, 1);
 
        //만나면 점 분리 할 수 없는 것
        
        bool meet = false;
 
        for (int i = 0; i < bHull.size()-1; i++) {
            for(int j = 0; j < wHull.size()-1; j++) {
                if (isCross(b[bHull[i]], b[bHull[i + 1]], w[wHull[j]], w[wHull[j + 1]])) {
                    meet = true;
                    break;
                }
            }
            if (meet) break;
        }
    
        if (meet) { //만나니까 분리할 수 없음
            cout << "NO" << '\n';
            continue;
        }
 
        //CCW가 모두 > 0 -> 하나가 나머지를 포함하는 것
        bool allPlus = true;
        for (int i = 0; i < bHull.size() - 1; i++) {
            for (int j = 0; j < wHull.size() - 1; j++) {
                if (ccw(b[bHull[i]], b[bHull[i + 1]], w[wHull[j]]) <= 0) {
                    allPlus = false;
                    break;
                }
            }
            if (!allPlus) 
                break;
        }
        if (allPlus) {
            cout << "NO\n";
            continue;
        }
 
        allPlus = true;
        for (int i = 0; i < wHull.size() - 1; i++) {
            for (int j = 0; j < bHull.size() - 1; j++) {
                if (ccw(w[wHull[i]], w[wHull[i + 1]], b[bHull[j]]) <= 0) {
                    allPlus = false;
                    break;
                }
            }
            if (!allPlus) break;
        }
        if (allPlus) {
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
    }
}