[2019 SCPC 2차 예선]

존의 정사각형

미국 일류 대학의 수학과에 재학중인 미국인 존은 정사각형 내부를 정사각형들의 합집합으로 채우는 방법에 대해 연구를 하다가 다음과 같은 문제를 생각하게 되었다.



왼쪽 아래 꼭지점의 좌표가 \((0,\ 0)\)이고 한 변의 길이가 \(M\)인 축에 평행한 정사각형을 \(U\)라고 하자.

정사각형 \(U\)의 내부에는 \(N\)개의 점들이 들어있으며 이들의 집합을 \(P\)라고 한다. 

\(P\)에 속한 각 점 \(p\)에 대해서 축에 평행한 정사각형 \(Q(p)\)는 다음과 같이 정의된다.

    1. \(Q(p)\)의 왼쪽 아래 꼭지점이 \(p\)위에 놓인다.

    2. \(Q(p)\)는 \(U\) 안에 (\(U\)의 경계 포함) 위치한다.

    3. \(Q(p)\)의 내부에는 \(P\)에 속한 어떤 점도 포함하지 않는다. 단, \(Q(p)\)의 경계에 \(P\)에 속한 점이 놓이는 것은 허용한다.

    4. \(Q(p)\)는 위의 세 조건을 만족하는 가장 큰 정사각형이다.



이러한 조건을 만족하는 정사각형 \(Q(p)\)는 각 점 \(p\)에 대해 유일하게 존재한다.



아래 그림은 \(P = \{\ p_1, p_2, p_3, p_4, p_5 \}\)에 5개의 점이 속해 있을 때, 위의 조건을 만족하는 5개의 정사각형 \(Q(p_1 ),Q(p_2 ),Q(p_3 ),Q(p_4 ),Q(p_5)\)를 모두 그린 것이다.



 





정사각형 \(U\)의 내부에 \(N\)개의 점들을 포함한 점 집합 \(P\)가 주어질 때, \(P\)에 속한 모든 점 \(p\)에 대해 위와 같이 정의된 정사각형 \(Q(p)\)의 한 변의 길이의 합을 출력하는 프로그램을 작성하시오.


입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,

이후 차례로  \(T\) 개의 테스트 케이스가 주어진다. \((1\le T\le22)\)

각 테스트 케이스의 첫 줄에는 한 개의 정수 \(M\ (2\le M \le 10^9)\)가 주어지며, 정사각형 \(U\)의 변의 길이를 의미한다. 

둘째 줄에는 역시 한 개의 정수 \(N\ (1≤N≤500,000)\)가 주어지며, 점 집합 \(P\)에 속한 점들의 개수를 의미한다.

다음 \(N\)개의 줄의 \(i\)번째 줄에는 두 정수 \(x_i,\ y_i\ (1≤x_i,\ y_i≤M-1)\)가 공백으로 구분되어 주어지며, 각 \((x_i,\ y_i)\)는 점 집합 \(P\)에 속한 점의 좌표를 의미한다.

각 테스트 케이스에서 입력으로 주어지는 점들의 좌표 중 정확히 같은 것은 없다.




출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.

그 다음 줄에, \(P\)에 속한 모든 점 \(p\)에 대해 위와 같이 정의된 정사각형 \(Q(p)\)의 한 변의 길이의 합을 정수형태로 출력하시오.

입출력예

입력
2
5
2
3 4
1 1
12
5
2 3
7 4
4 6
3 10
9 8
출력
Case #1
4
Case #2
17

돌아가기

댓글