15774번 - United States Of Eurasia 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 20 초 (추가 시간 없음) | 1024 MB | 170 | 24 | 18 | 17.308% |
문제
서기 5013년, 유라시아 대륙을 정복한 jh05013은 "jh나라" 를 건설하였다. 유라시아 대륙을 모두 망라하는 "jh나라"는 아주 넓고 인구 수가 많기 때문에, jh05013은 영토를 "지방"으로 분리하여 이들을 효율적으로 관리하려고 한다. jh나라에는 N개의 주택이 존재하고, 각각의 주택은 2차원 유클리드 좌표계의 (xi, yi) 위치에 존재한다. jh05013은 이들을 "지방"으로 분리할 때 다음과 같은 조건을 만족시킨다:
- 조건 1. 각각의 지방은 x좌표가 일정한 구간 안에 들어오는 주택들을 관리한다. (이때, 어떠한 지방이 모든 주택을 관리하거나, 어떤 주택도 관리하지 않을 수 있다.)
- 조건 2. 모든 주택은 정확히 하나의 지방에 의해서 관리되어야 한다.
- 조건 3. 최대 K개의 지방을 만들 수 있다.
유라시아 대륙에는 다양한 인종, 종교, 민족이 있다. 이들 간의 분쟁을 막으려면 최대한 각 지방의 분열을 줄여야 한다. 각 지역의 "분열도"의 정의는, 해당 지역이 관할하고 있는 주택 중, 가장 거리가 먼 쌍의 거리이다. 이때, 거리는 유클리드 거리로 기준으로 한다. 당신은 jh05013를 도와서, 각 지역의 "분열도"의 최댓값을 최소화하려고 한다.
입력
첫 번째 줄에 점의 개수 N, 지방의 개수 K가 공백으로 구분되어 주어진다.
이후 N개의 줄의 i번째 줄에는 두 정수 xi, yi가 공백으로 구분되어 주어진다. 이는 (xi, yi) 위치에 주택이 있다는 것이다.
출력
각 지역의 분열도의 최댓값의 최솟값을 M이라고 할 때, M2을 출력한다.
제한
- 1 ≤ K ≤ N ≤ 250,000
- 모든 주택의 좌표는 다르다. 즉, i ≠ j이면, xi ≠ xj 이거나 yi ≠ yj가 항상 성립한다.
- 0 ≤ xi, yi ≤ 109
서브태스크 1 (20점)
이 서브태스크는 다음의 조건을 만족한다.:
- N ≤ 500
서브태스크 2 (20점)
이 서브태스크는 다음의 조건을 만족한다.:
- N ≤ 5,000
서브태스크 3 (60점)
이 서브태스크는 추가 제한 조건이 없다.
예제 입력 1
4 2 101 100 2 5 100 101 4 3
예제 출력 1
8
예제 입력 2
4 4 3 1 4 1 5 1 9 2
예제 출력 2
0
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호