20193번 - 화려한 정사각형 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 512 MB | 389 | 130 | 90 | 30.928% |
문제
평면에 N개의 점 P1(x1, y1), P2(x2, y2), . . . , PN(xN, yN)이 주어지며, 각각의 점들은 총 K개의 색깔 중 하나를 가지고 있다. 각 점의 색깔은 {1, 2, . . . , K} 중의 한 정수로 표현된다.
어떤 정사각형이 각 K개의 색깔에 대해 해당 색깔의 점을 하나 이상 포함하고 있다면, 이 정사각형을 화려한 정사각형이라고 부른다. 변의 길이를 최소로 하는 화려한 정사각형을 찾아서 그 변의 길이를 출력하는 프로그램을 작성하라.
단, 여기서 정사각형은 네 변이 모두 수평 혹은 수직인 것에 한정하며, 정사각형의 내부가 아닌 경계에 놓인 점들도 그 정사각형에 포함된다고 생각한다. 정사각형의 한 변의 길이가 0이 되어 점으로 나타나는 경우도 정사각형의 한 경우로 간주한다.
입력
첫 번째 줄에 두 정수 N과 K가 공백 하나를 사이로 두고 주어진다.
이후 N 개의 줄이 주어진다. 이 중 i 번째 줄에는 세 개의 정수 xi, yi, ki가 공백 하나 씩을 사이에 두고 주어지며, 입력으로 주어지는 각 점의 좌표 (xi, yi)와 그 점의 색깔 ki을 의미한다.
출력
첫 번째 줄에 문제의 정답을 출력한다.
제한
- 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 | 추가 제약 조건 없음 |
예제 입력 1
5 2 4 2 1 5 3 1 5 4 2 4 5 2 3 8 2
예제 출력 1
1
예제 입력 2
5 3 4 2 1 5 3 1 5 4 2 4 5 2 3 8 3
예제 출력 2
5
예제 입력 3
4 2 1 1 1 1 1 1 1 1 2 1 1 2
예제 출력 3
0
출처
Olympiad > 한국정보올림피아드 > KOI 2020 2차대회 > 중등부 4번
Olympiad > 한국정보올림피아드 > KOI 2020 2차대회 > 고등부 3번
Camp > Petrozavodsk Programming Camp > Winter 2021 > Day 9: Grand Prix of Suwon C번
Contest > Open Cup > 2020/2021 Season > Stage 13: Grand Prix of Suwon C번
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2022 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호