점 분리
시간 제한1초메모리 제한128 MB
평면 위 두 색깔의 점 집합을 하나의 직선으로 분리할 수 있는지 판별하는 문제로, 본질적으로 두 점 집합의 볼록 껍질 분리 여부를 확인해야 합니다.
문제
평면 위에 여러 개의 검은 점과 흰 점이 있다. 이때 길이가 무한대인 직선 하나를 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 나누어지는 두 그룹 중 한 그룹에는 흰 점만, 다른 그룹에는 검은 점만 있어야 한다.
아래 그림에서 가장 왼쪽 예제는 점선으로 표시된 직선으로 두 종류의 점을 나눌 수 있다. 하지만 나머지 예제는 직선으로 점을 분리할 수 없다.
흰 점과 검은 점의 좌표가 주어졌을 때, 직선으로 점을 분리할 수 있는지 없는지를 판별하는 프로그램을 작성하시오.
입력
첫째 줄에는 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스의 첫째 줄에는 검은 점의 개수 과 흰 점의 개수 이 공백으로 구분되어 주어진다. 과 은 보다 작거나 같다. 이어지는 개의 줄에는 검은 점의 좌표가 공백으로 구분되어 주어지고, 그다음 개의 줄에는 흰 점의 좌표가 주어진다.
모든 점의 , 좌표는 보다 크거나 같고 보다 작거나 같은 정수이다. 또한, 같은 위치에 점이 두 개 이상 있는 경우는 없다.
출력
각 테스트 케이스에 대해, 문제의 설명대로 직선으로 점을 분리할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.