정사각형 수영장
면접 대비시간 제한1초메모리 제한1024 MB
N x N 마당에 T개의 나무가 있을 때, 나무를 포함하지 않는 가장 큰 정사각형의 한 변 길이를 구한다.
문제
Ron은 한 변의 길이가 N인 정사각형 마당에 정사각형 수영장을 만들려고 하는데, 마당에는 나무 T그루가 있다. 만들 수 있는 가장 큰 정사각형 수영장의 한 변의 길이를 구하시오.
입력
첫째 줄에 정수 N이 주어진다. N ≥ 2이다. 둘째 줄에 양의 정수 T가 주어진다. T < N2이다. 이어서 T개의 줄이 주어지며, 각 줄은 나무 한 그루의 위치를 나타낸다. 위치는 두 양의 정수 R과 C가 공백 하나를 사이에 두고 주어진다. 나무는 R행 C열에 있으며, 행은 위에서 아래로 1부터 N까지, 열은 왼쪽에서 오른쪽으로 1부터 N까지 번호가 매겨진다. 두 나무가 같은 위치에 있는 경우는 없다.
출력
Ron의 마당에 완전히 포함되면서 T그루의 나무를 하나도 포함하지 않는 M×M 정사각형이 존재하도록 하는 가장 큰 양의 정수 M을 한 줄에 출력한다.