전국시대 (Sengoku)
시간 제한0.75초메모리 제한1024 MB
L×L 격자에 N명의 감시병이 배치될 때, (x, y)에 있는 감시병이 |x-i| = |y-j|인 모든 칸을 감시한다. 감시병이 하나 이상 지키는 칸의 수를 구한다.
문제
전국시대가 한창이다. JOI 나라를 이끄는 JOI 무장은 다가올 전쟁에 대비해 자신의 영지에 감시병을 배치하기로 했다.
JOI 나라의 영지는 동서 폭과 남북 폭이 L인 정사각형 모양이다. 영지는 1 × 1 크기의 정사각형 구역으로 나뉘어 있으며, 각 구역은 0 ≤ x < L, 0 ≤ y < L을 만족하는 정수 x, y로 (x, y)라고 표현된다. 구역 (0, 0)은 북서쪽 모퉁이 구역이고, 구역 (x, y)는 구역 (0, 0)에서 동쪽으로 x, 남쪽으로 y만큼 떨어진 지점에 있는 구역이다.
각 감시병은 영지 안의 한 구역에 머무르며 다음과 같은 범위를 감시한다. (x, y)에 있는 감시병은 조건 |x − i| = |y − j|를 만족하는 영지 안의 모든 구역 (i, j)를 감시한다 (이 범위는 다른 감시병의 위치에 따라 변하지 않는다). 한 구역에 두 명 이상의 감시병이 있는 경우는 없다.
JOI 무장이 배치한 N명의 감시병 위치가 주어질 때, 적어도 한 명 이상의 감시병이 감시하는 영지 안의 구역 개수를 구하는 프로그램을 작성하시오.
입력
표준 입력에서 다음 입력을 읽는다.
- 첫째 줄에 정수 L과 N이 공백을 구분으로 쓰여 있다.
- 이어지는 N개 줄은 한 줄에 한 명의 감시병을 설명한다. 이 줄들 중 i번째 줄은 i번째 감시병을 설명하며, 정수 xi와 yi (0 ≤ xi < L, 0 ≤ yi < L)가 공백을 구분으로 쓰여 있다.
출력
표준 출력에 다음 데이터를 출력한다.
- 첫째 줄에는 한 명 이상의 감시병이 감시하는 구역 개수를 나타내는 정수 하나가 포함되어야 한다.
제한
- 1 ≤ L ≤ 100, 000, 000, 영지의 한 변의 길이
- 1 ≤ N ≤ 100, 000, 감시병의 수
힌트
이때의 JOI 나라를 그림으로 나타내면 아래와 같다. 감시되는 구역의 개수는 18이다 (검은 원은 감시병을 나타낸다. 감시되는 구역은 회색으로 표시되어 있다).
