만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

종전 협상

면접 대비

시간 제한2초메모리 제한512 MB

요약
두 나라의 도시 좌표가 주어질 때, 각 나라의 도시를 서로 반대편에만 두는 직선이 존재하는지 판정한다.
난이도

보통10점 중 6점

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

문제

nein 나라가 sys 나라를 침공했지만 sys 나라는 공격을 막아냈다. 두 나라는 이제 국경선을 다시 긋는 종전 협상을 한다. 새 국경선은 평면 위의 직선 하나이고, nein 나라가 차지한 도시는 모두 직선의 한쪽에, sys 나라가 차지한 도시는 모두 반대쪽에 놓여야 한다. 직선 위에 도시가 있으면 국경선으로 쓸 수 없다. 조건을 만족하는 직선이 아예 없을 수도 있으니, 그런 직선이 존재하는지 판정하라.

입력

첫째 줄에 nein 나라의 도시 수 nn과 sys 나라의 도시 수 mm이 주어진다. (1≤n,m≤10001 \le n, m \le 1000)

다음 nn개 줄에는 nein 나라가 차지한 도시의 좌표 xx와 yy가 주어진다.

그다음 mm개 줄에는 sys 나라가 차지한 도시의 좌표 xx와 yy가 주어진다.

좌표는 모두 정수이고 −106≤x,y≤106-10^6 \le x, y \le 10^6이다. 같은 위치에 도시가 두 개 있는 경우는 없다.

출력

두 나라의 도시를 완전히 갈라놓는 직선이 있으면 YES를, 없으면 NO를 출력한다.

예제2

  1. 예제 1

    입력
    3 3
    1 1
    2 2
    3 3
    1 2
    2 3
    3 4
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    3 1
    0 0
    10 0
    0 10
    2 2
    
    예상 출력
    NO