적인가 아군인가?
시간 제한1초메모리 제한128 MB
3차원 점 두 집합이 주어질 때, 한 평면으로 제국 점들은 양의 쪽에, 동맹 점들은 음이 아닌 쪽에 분리할 수 있는지 판정한다.
문제
루크는 반란 연합(Alliance)의 항성계와 제국(Empire)의 항성계를 구분하는 데 어려움을 겪고 있다. 그는 제국과 연합에 속한 모든 항성계의 좌표를 알고 있지만, 워프 속도에서는 목록을 일일이 찾아볼 시간이 없다.
그의 조준 컴퓨터는 구형 모델이라 다음 부등식의 참/거짓만 계산할 수 있다.
ax + by + cz + d > 0
여기서 는 항성계의 좌표이고 는 실수 계수이다. 를 하나로 고정하면 모든 항성계가 한 번에 분류된다. 부등식이 참이면 그 항성계를 제국으로, 아니면 연합으로 판정한다.
이 분류기는 두 집단을 하나의 평면으로 분리할 수 있을 때에만 쓸모가 있다. 즉 모든 제국 항성계에 대해 부등식이 성립하고 어떤 연합 항성계에 대해서도 성립하지 않는 실수 가 존재해야 한다. 각 테스트 케이스마다 그러한 계수가 존재하는지 판정하여라.
입력
입력은 여러 개의 테스트 케이스로 이루어지며, 마지막에 -1 -1이 적힌 줄이 온다.
각 테스트 케이스는 연합 항성계의 개수가 적힌 줄로 시작한다. 이어지는 각 줄에는 연합 항성계 하나의 정수 좌표 이 주어진다. 그다음 제국 항성계의 개수가 주어지고, 각 제국 항성계의 정수 좌표가 한 줄에 하나씩 주어진다. 제국과 연합을 합한 항성계는 최소 개, 최대 개이며, 모든 항성계의 좌표는 서로 다르다.
출력
각 테스트 케이스마다 한 줄에, 모든 제국 항성계에 대해 이고 모든 연합 항성계에 대해 인 실수 계수 가 존재하면 YES를, 존재하지 않으면 NO를 출력하여라.