백준 3878 (C++) 점 분리

최초 업로드: 2025-08-13 13:03:09

최근 수정 시간: 2025-08-13 13:03:37

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] 점 분리

[문제 링크](https://www.acmicpc.net/problem/3878)

## 문제 설명

평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 중 한 그룹에는 흰 점만 있어야 하고, 다른 그룹에는 검은 점만 있어야 한다.

아래 그림에서 제일 왼쪽 예제는 점선으로 표시된 직선으로 두 점을 나눌 수 있다. 하지만 나머지 예제는 직선으로 점을 분리할 수 없다.

흰 점과 검은 점의 좌표가 주어졌을 때, 직선으로 점을 분리할 수 있는지 없는지를 알아내는 프로그램을 작성하시오.

## 입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에 검정 점의 개수 n과 흰 점의 개수 m이 공백으로 구분되어 주어진다. n과 m은 100보다 작거나 같다. 다음 줄부터 n개의 줄에는 검정 점의 좌표가 공백으로 구분되어 주어진다. 그 다음 m개의 줄에는 흰 점의 좌표가 주어진다.

모든 점의 x, y좌표는 0보다 크거나 같고, 10000보다 작거나 같은 정수이다. 또한, 같은 위치에 점이 2개 이상 있는 경우는 없다.

## 출력

각각의 테스트 케이스에 대해서, 점을 문제의 설명대로 분리할 수 있으면 YES를, 아니면 NO를 출력한다.

## 풀이
#### 하얀색 볼록다각형과, 검은색 볼록다각형을 만든 후, 하얀색 다각형 내에 검은색 점이 있는 경우, 검은색 다각형 내에 하얀색 점이 있는 경우, 하얀색 선과 검은색 선이 만나는 경우 세 가지를 확인하면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct pos {
 ll x, y, p=0, q=0;
 bool operator<(const pos o) {
 if(p*o.q!=q*o.p) return p*o.q > q*o.p;
 if(y!=o.y) return y < o.y;
 return x < o.x;
 }
};

int ccw(pos a, pos b, pos c) {
 pos vec1 = {b.x-a.x, b.y-a.y};
 pos vec2 = {c.x-a.x, c.y-a.y};
 ll ret = vec1.x*vec2.y - vec1.y*vec2.x;
 if(ret>0) return 1;
 if(ret<0) return -1;
 return 0;
}

bool isInside(vector<pos> stk, pos point) {
 if(stk.size()<=2) return false;
 for(int i=0;i<stk.size();i++) {
 if(ccw(stk[i], stk[(i+1)%stk.size()], point)<=0) return false;
 }
 return true;
}

bool isIntersect(pos a, pos b, pos c, pos d) {
    int aToB1 = ccw(a, b, c);
    int aToB2 = ccw(a, b, d);
    int bToA1 = ccw(c, d, a);
    int bToA2 = ccw(c, d, b);

if(aToB1*aToB2==0 && bToA1*bToA2==0) {
 return (min(a.x, b.x)<=c.x && c.x<=max(a.x, b.x) || min(a.x, b.x)<=d.x && d.x<=max(a.x, b.x) || min(c.x, d.x)<=a.x && a.x<=max(c.x, d.x) || min(c.x, d.x)<=b.x && b.x<=max(c.x, d.x))
 && (min(a.y, b.y)<=c.y && c.y<=max(a.y, b.y) || min(a.y, b.y)<=d.y && d.y<=max(a.y, b.y) || min(c.y, d.y)<=a.y && a.y<=max(c.y, d.y) || min(c.y, d.y)<=b.y && b.y<=max(c.y, d.y));
 }
 return aToB1*aToB2<=0 && bToA1*bToA2<=0;
}

bool chk(vector<pos> whiteStk, vector<pos> blackStk) {
 int n = whiteStk.size();
 int m = blackStk.size();

// 검은 도형 내에 하얀 점
    for(pos point : blackStk) {
        if(isInside(whiteStk, point)) return false;
    }

// 하얀 도형 내에 검은 점
    for(pos point : whiteStk) {
        if(isInside(blackStk, point)) return false;
    }

// 두 선분의 충돌
 for(int i=0;i<n;i++) {
 for(int j=0;j<m;j++) {
 if(isIntersect(whiteStk[i], whiteStk[(i+1)%n], blackStk[j], blackStk[(j+1)%m])) return false;
 }
 }
 return true;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;

while(t--) {
 int n, m; cin >> n >> m;
 vector<pos> white(n), black(m);
 for(int i=0;i<n;i++) cin >> white[i].x >> white[i].y;
 for(int i=0;i<m;i++) cin >> black[i].x >> black[i].y;

sort(white.begin(), white.end());
 for(int i=0;i<n;i++) {
 white[i].p = white[i].x - white[0].x;
 white[i].q = white[i].y - white[0].y;
 }
 sort(white.begin(), white.end());

vector<pos> whiteStk;
 for(int i=0;i<n;i++) {
 while(whiteStk.size()>=2 && ccw(whiteStk[whiteStk.size()-2], whiteStk[whiteStk.size()-1], white[i])<=0) whiteStk.pop_back();
 whiteStk.push_back(white[i]);
 }

sort(black.begin(), black.end());
 for(int i=0;i<m;i++) {
 black[i].p = black[i].x - black[0].x;
 black[i].q = black[i].y - black[0].y;
 }
 sort(black.begin(), black.end());

vector<pos> blackStk;
 for(int i=0;i<m;i++) {
 while(blackStk.size()>=2 && ccw(blackStk[blackStk.size()-2], blackStk[blackStk.size()-1], black[i])<=0) blackStk.pop_back();
 blackStk.push_back(black[i]);
 }
 cout << (chk(whiteStk, blackStk) ? "YES\n" : "NO\n");
 }
}
```