KOI 2차 2020 중4/고3- 화려한 정사각형 > 문제은행 : 정보올림피아드&알고리즘




4605 : 화려한 정사각형

제한시간
1000 ms   
메모리제한
1024 MB   
해결횟수
0 회   
시도횟수
0 회   

문제

평면에 N개의 점 P1(x1, y1), P2(x2, y2), . . . , PN (xN , yN )이 주어지며, 각각의 점들은 총 K개의 색깔 중 하나를 가지고 있다. 각 점의 색깔은 {1, 2, . . . , K} 중의 한 정수로 표현된다.

 

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

 

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

 


제약 조건


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

 


부분문제


  1. (3점) N ≤ 50, 모든 i (1 ≤ i ≤ N)에 대해 xi, yi ≤ 50
  2. (10점) K ≤ 50, 모든 i (1 ≤ i ≤ N)에 대해 xi, yi ≤ 2,500
  3. (12점) K = 2.
  4. (5점) N ≤ 50.
  5. (8점) N ≤ 150.
  6. (9점) N ≤ 600.
  7. (13점) N ≤ 2,500.
  8. (40점) 추가 제약 조건 없음.​

입력형식

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

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


출력형식

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

 


입력 예

5 2
4 2 1
5 3 1
5 4 2
4 5 2
3 8 2

출력 예

1

입력 예

5 3
4 2 1
5 3 1
5 4 2
4 5 2
3 8 3

출력 예

5

입력 예

4 2
1 1 1
1 1 1
1 1 2
1 1 2

출력 예

0


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP