아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

슈퍼 페인트볼

면접 대비

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

요약
N×N 격자에 놓인 최대 100000개의 상대 위치가 주어질 때, 자신의 행, 열, 두 대각선 중 하나가 모든 상대를 지나가는 칸의 수를 센다.
난이도

보통10점 중 6점

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

문제

베시가 정사각형 벌판에서 페인트볼 게임을 하고 있습니다. 벌판은 N×NN \times N개의 단위 칸으로 나뉘어 있습니다 (1≤N≤1001 \le N \le 100). 상대는 모두 KK명이며 (1≤K≤100,0001 \le K \le 100{,}000), ii번째 상대는 RiR_i행 CiC_i열의 칸에 서 있습니다 (1≤Ri≤N1 \le R_i \le N, 1≤Ci≤N1 \le C_i \le N). 여러 상대가 같은 칸에 서 있을 수도 있습니다.

베시의 페인트볼 총은 상, 하, 좌, 우와 네 대각선 방향(왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래)까지 모두 여덟 방향으로 발사할 수 있습니다. 어떤 상대가 베시가 서 있는 칸과 같은 행, 같은 열, 또는 그 칸을 지나는 두 대각선 중 하나 위에 있으면 그 상대를 맞힐 수 있습니다. 베시와 같은 칸에 있는 상대도 맞힐 수 있습니다.

베시는 정확히 한 칸에 섭니다. N×NN \times N개의 칸 중에서, 그 칸에 섰을 때 KK명의 상대를 모두 맞힐 수 있는 칸이 몇 개인지 세어 주세요.

입력

  • 첫째 줄: 공백으로 구분된 두 정수 NN과 KK.
  • 둘째 줄부터 K+1K+1째 줄까지: i+1i+1째 줄에는 ii번째 상대의 행과 열을 나타내는 두 정수 RiR_i와 CiC_i가 공백으로 구분되어 주어집니다.

출력

  • 첫째 줄: 베시가 모든 상대를 맞힐 수 있도록 설 수 있는 서로 다른 칸의 개수를 나타내는 정수 하나.

힌트

44행 44열의 벌판에 상대가 (2,1)(2,1), (2,3)(2,3), (4,1)(4,1)에 있다고 합시다 (C는 상대의 위치입니다):

. . . .
C . C .
. . . .
C . . .

(2,1)(2,1), (2,3)(2,3), (3,2)(3,2), (4,1)(4,1), (4,3)(4,3) 이 다섯 칸 각각에서 베시는 세 상대를 모두 맞힐 수 있으므로 답은 55입니다. 아래 그림에서 B는 베시가 설 수 있는 칸이고, *는 베시가 설 수 있으면서 동시에 상대도 있는 칸입니다:

. . . .        . . . .
B . B .        * . * .
. B . .   =>   . B . .
B . B .        * . B .

예제3

  1. 예제 1

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

    입력
    1 1
    1 1
    
    예상 출력
    1
    
  3. 예제 3

    입력
    3 1
    1 1
    
    예상 출력
    7