14273번 - 영선이의 생일

오늘은 영선이의 생일이다. 영선이의 친구들은 영선이를 위한 직사각형 모양의 생일 케이크를 하나 준비했다.

케이크의 윗면은 총 n×m개의 칸으로 나누어져 있다. 가장 왼쪽 윗칸의 좌표는 (1, 1)이고, 오른쪽 윗칸의 좌표는 (n, 1), 오른쪽 아랫칸의 좌표는 (n, m)이다.

7개의 칸에는 아래와 같은 장식이 놓여져 있다.

• (x1, y1)에는 초가 놓여져 있다.
• (x2, y2), (x3, y3), (x4, y4)에는 체리가 놓여져 있다.
• (x5, y5), (x6, y6), (x7, y7)에는 딸기가 놓여져 있다.

영선이는 케이크를 4조각으로 나누려고 한다. 한 조각은 영선이가 먹을 것이고, 나머지 조각들은 친구들이 먹을 것이다.

네 조각은 모두 칸으로 이루어져 있어야 하며, 각각의 칸은 반드시 하나의 조각에 포함되어 있어야 한다.

영선이는 초가 포함되어 있는 조각을 먹어야 하고, 나머지 세 조각에는 하나의 딸기와 하나의 체리가 포함되어 있어야 한다. 또한, 모든 조각은 연결되어 있어야 한다.

n과 m, 그리고 초, 체리, 딸기의 위치가 주어졌을 때, 문제의 조건을 만족하게 케이크를 나눌 수 있는지 없는지 구하는 프로그램을 작성하시오.

첫째 줄에 n과 m이 주어진다. (1 ≤ n, m ≤ 1,000,000,000)

둘째 줄부터 7개의 줄에 (x1, y1), (x2, y2), ..., (x7, y7)이 주어진다.

적어도 7개의 칸으로 이루어져 있는 케이크만 입력으로 주어진다. (x1, y1), (x2, y2), ..., (x7, y7)은 서로 다르다.

첫째 줄에 문제의 조건에 맞게 케이크를 4조각 내는 것이 가능하면 "Yes"를, 불가능하면 "No"를 출력한다.

예제 3의 경우 다음과 같은 그림으로 나타낼 수 있다.