평면에 N개의 점 \(P\)_\(1\)(\(x\)_\(1\), \(y\)_\(1\)), P_\(2\)(\(x\)_\(2\), \(y\)_\(2\)), . . . , P_\(N\)(\(x\)_\(N\), \(y\)_\(N\))이 주어지며, 각각의 점들은 총 \(K\)개의 색깔 중 하나를 가지고 있다. 각 점의 색깔은 {\(1\), \(2\), . . . , \(K\)} 중의 한 정수로 표현된다.

어떤 정사각형이 각 \(K\)개의 색깔에 대해 해당 색깔의 점을 하나 이상 포함하고 있다면, 이 정사각형을 화려한 정사각형이라고 부른다. 변의 길이를 최소로 하는 화려한 정사각형을 찾아서 그 변의 길이를 출력하는 프로그램을 작성하라.

단, 여기서 정사각형은 네 변이 모두 수평 혹은 수직인 것에 한정하며, 정사각형의 내부가 아닌 경계에 놓인 점들도 그 정사각형에 포함된다고 생각한다. 정사각형의 한 변의 길이가 \(0\)이 되어 점으로 나타나는 경우도 정사각형의 한 경우로 간주한다.

• \(2 ≤ N ≤ 100,000\)
• \(2 ≤ K ≤ N\)
• 모든 \(i\) (\(1 ≤ i ≤ N\))에 대해, \(x_i\)와 \(y_i\)는 \(1\) 이상 \(250,000\) 이하의 정수이다.
• 모든 색 \(k\) (\(1 ≤ k ≤ K\))에 대해, \(N\)개의 점들 중 색깔이 \(k\)인 점이 최소 하나 존재한다.

첫 번째 줄에 두 정수 \(N\)과 \(K\)가 공백 하나를 사이로 두고 주어진다.

이후 \(N\) 개의 줄이 주어진다. 이 중 \(i\) 번째 줄에는 세 개의 정수 \(x\)_\(i\), \(y\)_\(i\), \(k\)_\(i\)가 공백 하나 씩을 사이에 두고 주어지며, 입력으로 주어지는 각 점의 좌표 (\(x\)_\(i\), \(y\)_\(i\))와 그 점의 색깔 \(k\)_\(i\)을 의미한다.

첫 번째 줄에 문제의 정답을 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2020 > 2차 대회 > 중등부 4번 / 고등부 3번