페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4605
서브태스크

화려한 정사각형 5초 1024MB

문제

평면에 N개의 점 P_1(x_1, y_1), P_2(x_2, y_2), \cdots , P_N (x_N , y_N )이 주어지며, 각각의 점들은 총 K개의 색깔 중 하나를 가지고 있다. 각 점의 색깔은 \{1, 2,\ \cdots , K\} 중의 한 정수로 표현된다.

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

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


입력

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

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

제약 조건

  • 2 ≤ N ≤ 100,000

  • 2 ≤ K ≤ N

  • 모든 i (1 ≤ i ≤ N)에 대해, x_i와 y_i는 1 이상 250,000 이하의 정수이다.

  • 모든 색 k (1 ≤ k ≤ K)에 대해, N개의 점들 중 색깔이 k인 점이 최소 하나 존재한다.


출력

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


부분문제

번호 점수 조건
#13점

N ≤ 50, 모든 i (1 ≤ i ≤ N)에 대해 x_i, y_i ≤ 50

#210점

K ≤ 50, 모든 i (1 ≤ i ≤ N)에 대해 x_i, y_i ≤ 2,500

#312점

k = 2

#45점

N ≤ 50

#58점

N ≤ 150

#69점

N ≤ 600

#713점

N ≤ 2,500

#840점

추가 제약 조건 없음.​


예제1

입력
52

421

531

542

452

382
출력
1

예제2

입력
53

421

531

542

452

383
출력
5

예제3

입력
42

111

111

112

112
출력
0

출처

KOI 2차 2020 중4/고3

역링크 공식 문제집만