적인가 아군인가?

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

요약
3차원 점 두 집합이 주어질 때, 한 평면으로 제국 점들은 양의 쪽에, 동맹 점들은 음이 아닌 쪽에 분리할 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
기하, 수학, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

루크는 반란 연합(Alliance)의 항성계와 제국(Empire)의 항성계를 구분하는 데 어려움을 겪고 있다. 그는 제국과 연합에 속한 모든 항성계의 x,y,zx, y, z 좌표를 알고 있지만, 워프 속도에서는 목록을 일일이 찾아볼 시간이 없다.

그의 조준 컴퓨터는 구형 모델이라 다음 부등식의 참/거짓만 계산할 수 있다.

ax + by + cz + d > 0

여기서 x,y,zx, y, z는 항성계의 좌표이고 a,b,c,da, b, c, d는 실수 계수이다. a,b,c,da, b, c, d를 하나로 고정하면 모든 항성계가 한 번에 분류된다. 부등식이 참이면 그 항성계를 제국으로, 아니면 연합으로 판정한다.

이 분류기는 두 집단을 하나의 평면으로 분리할 수 있을 때에만 쓸모가 있다. 즉 모든 제국 항성계에 대해 부등식이 성립하고 어떤 연합 항성계에 대해서도 성립하지 않는 실수 a,b,c,da, b, c, d가 존재해야 한다. 각 테스트 케이스마다 그러한 계수가 존재하는지 판정하여라.

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 마지막에 -1 -1이 적힌 줄이 온다.

각 테스트 케이스는 연합 항성계의 개수가 적힌 줄로 시작한다. 이어지는 각 줄에는 연합 항성계 하나의 정수 좌표 −100≤x,y,z≤100-100 \le x, y, z \le 100이 주어진다. 그다음 제국 항성계의 개수가 주어지고, 각 제국 항성계의 정수 좌표가 한 줄에 하나씩 주어진다. 제국과 연합을 합한 항성계는 최소 11개, 최대 200200개이며, 모든 항성계의 좌표는 서로 다르다.

출력

각 테스트 케이스마다 한 줄에, 모든 제국 항성계에 대해 ax+by+cz+d>0ax + by + cz + d > 0이고 모든 연합 항성계에 대해 ax+by+cz+d≤0ax + by + cz + d \le 0인 실수 계수 a,b,c,da, b, c, d가 존재하면 YES를, 존재하지 않으면 NO를 출력하여라.

예제3

  1. 예제 1

    입력
    2
    -93 48 -92
    -62 12 -32
    8
    51 98 -61
    -3 72 81
    95 25 22
    89 43 -99
    100 -2 -96
    -18 45 -63
    36 -21 -8
    71 -24 42
    -1 -1
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    1
    -5 0 0
    1
    5 0 0
    -1 -1
    
    예상 출력
    YES
    
  3. 예제 3

    입력
    1
    0 0 0
    2
    -2 0 0
    2 0 0
    -1 -1
    
    예상 출력
    NO