34064번 - 밤(Time For The Moon Night)

문제

떨려오는 별빛 반짝이는데

넌 어디를 보고 있는지

금방이라도 사라질 것 같은데

나는 밤하늘을 달려 너에게 가려고 한다. 밤하늘은 $N\times M$ 크기의 격자로 표현되며, 각 칸은 $(1,1)$부터 $(N,M)$까지의 좌표로 나타낼 수 있다. 나는 밤하늘에서 상하좌우 방향으로 한 칸씩 이동할 수 있다.

이 격자에는 $K$개의 별이 존재하며, 이중 $i$번째 별은 격자의 특정 칸 $(X_i,Y_i)$를 온전히 차지하고 있다. 따라서 별이 있는 칸으로는 이동할 수 없다.

나는 $(a_1,b_1)$과 $(a_2,b_2)$를 각각 왼쪽 아래와 오른쪽 위 꼭짓점으로 하는 축에 평행한 직사각형 안에서, 별이 위치하지 않은 원하는 좌표에서 출발할 수 있다. 마찬가지로, 너는 $(a_3,b_3)$와 $(a_4,b_4)$를 각각 왼쪽 아래와 오른쪽 위 꼭짓점으로 하는 축에 평행한 직사각형 안에서 별이 위치하지 않은 원하는 좌표에서 시작할 수 있다.

내가 상하좌우로 인접한 칸으로 이동해 가며 너를 만나러 갈 수 있는 시작 위치의 조합의 수를 구해야 한다. 시작 위치 조합이 다르다는 것은 나의 시작 위치와 너의 시작 위치 중 하나 이상이 다르다는 것을 의미한다. 두 사람이 같은 위치에서 시작할 수 있다는 점에 유의하라.

입력

첫째 줄에 격자의 크기를 나타내는 두 정수 $N,M$과 별의 개수 $K$가 공백으로 구분되어 주어진다.

둘째 줄부터 $K$개의 줄에 걸쳐, 그중 $i$번째 줄에는 $i$번째 별의 위치를 나타내는 $X_i,Y_i$가 공백으로 구분되어 주어진다.

그다음 4개의 줄에 걸쳐, 그중 $i$번째 줄에는 $a_i,b_i$가 공백으로 구분되어 주어진다.

출력

상하좌우로 이동해서 두 사람이 만날 수 있는 시작 위치 조합의 수를 출력하라.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\le N,M\le 500$
• 0ドル\le K\le N\times M$
• 1ドル\le X_i\le N$ (1ドル\le i\le K$)
• 1ドル\le Y_i\le M$ (1ドル\le i\le K$)
• 별의 위치는 모두 서로 다르다. 즉, $i\ne j$ 이면 $X_i\ne X_j$ 또는 $Y_i\ne Y_j$이다.
• 1ドル\le a_i\le N$ (1ドル\le i\le 4$)
• 1ドル\le b_i\le M$ (1ドル\le i\le 4$)
• $a_1\le a_2$; $b_1\le b_2$
• $a_3\le a_4$; $b_3\le b_4$

정답이 32비트 정수 범위를 넘을 수 있으므로, C/C++에서는 long long, Java에서는 long과 같은 자료형을 사용하는 것을 권장한다.

노트

[フレーム]