점 분리

시간 제한1초메모리 제한128 MB

요약
평면 위 두 색깔의 점 집합을 하나의 직선으로 분리할 수 있는지 판별하는 문제로, 본질적으로 두 점 집합의 볼록 껍질 분리 여부를 확인해야 합니다.
난이도

보통10점 중 6점

유형
기하, 수학
정답자
아직 제출이 없습니다

문제

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

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

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

입력

첫째 줄에는 테스트 케이스의 개수 TT가 주어진다. 각 테스트 케이스의 첫째 줄에는 검은 점의 개수 nn과 흰 점의 개수 mm이 공백으로 구분되어 주어진다. nn과 mm은 100100보다 작거나 같다. 이어지는 nn개의 줄에는 검은 점의 좌표가 공백으로 구분되어 주어지고, 그다음 mm개의 줄에는 흰 점의 좌표가 주어진다.

모든 점의 xx, yy좌표는 00보다 크거나 같고 1000010000보다 작거나 같은 정수이다. 또한, 같은 위치에 점이 두 개 이상 있는 경우는 없다.

출력

각 테스트 케이스에 대해, 문제의 설명대로 직선으로 점을 분리할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

예제1

  1. 예제 1

    입력
    10
    3 3
    100 700
    200 200
    600 600
    500 100
    500 300
    800 500
    3 3
    100 300
    400 600
    400 100
    600 400
    500 900
    300 300
    3 4
    300 300
    500 300
    400 600
    100 100
    200 900
    500 900
    800 100
    1 2
    300 300
    100 100
    500 500
    1 1
    100 100
    200 100
    2 2
    0 0
    500 700
    1000 1400
    1500 2100
    2 2
    0 0
    1000 1000
    1000 0
    0 1000
    3 3
    0 100
    4999 102
    10000 103
    5001 102
    10000 102
    0 101
    3 3
    100 100
    200 100
    100 200
    0 0
    400 0
    0 400
    3 3
    2813 1640
    2583 2892
    2967 1916
    541 3562
    9298 3686
    7443 7921
    
    예상 출력
    YES
    NO
    NO
    NO
    YES
    YES
    NO
    NO
    NO
    YES