https://www.acmicpc.net/problem/10454
문제 요약
- -10억 ~ 10억 좌표에 10만개 점이 찍힘
- 정사각형 3개로 모든 점을 가리려고 함
- 최소 정사각형 크기는? (0도 가능함)
접근법
- 만약에 2차원이 아니고 1차원이라면? 정사각형이 아니라 선분으로 가린다면?
- 적당한 크기 k를 정해서 되는지 확인
- 되면 k를 줄여보고, 안되면 k를 늘려보고 : 파라메트릭 서치
- x 든 y든 최대, 최소인 부분에는 정사각형이 걸칠 것이다 + 파라메트릭 서치 이용
- 우선 한 방향만 생각해본다. y 좌표만 고려한다고 보면
- 적당한 k를 정해서 y 좌표가 다 커버가 되는지 본다
- 커버가 된다면 총 세부분으로 나뉠 것임
- 하지만 x 방향도 고려하기 때문에 이때 나눈 y의 경계를 그대로 사용하지는 못함
- 첫번째 부분이 k의 크기로 로 y 좌표가 커버가 되었다고 쳐도, x 방향으로는 k의 크기로 커버가 안될 수도 있다.
- x방향의 왼쪽 끝이든, 오른쪽끝이든 바싹 붙여서 k 만큼 포함을 시켜본다.
- 여기까지 하면 정사각형 하나를 사용한 결과가 됨
- 그러면 남는 점들이 생길 것임
- y만 기준으로 세 부분으로 나눌때랑은 다른 결과가 나올 것임
- 한번 더 반복
- 여기까지 하면 정사각형 두개를 사용한 결과가 됨
- 나머지 점들이 정사각형 범위에 포함되는지 확인
- 여기까지 하면 정사각형 세개를 사용한 결과가 됨
- 적당한 k를 정해서 y 좌표가 다 커버가 되는지 본다
- 좀더 다듬어보면
- k를 정함
- 주어진 점에서 (y최소 + k) 만큼 점을 선별 : O(n)
- 선별된 점에서 (x최소 + k) 만큼 점을 선별 : O(n), 첫번째 정사각형 완성
- 1차가 끝나고 나머지 점에서 (y최소 + k) 만큼 점을 선별 : O(n)
- 선별된 점에서 (x최소 + k) 만큼 점을 선별 : O(n), 두번째 정사각형 완성
- 나머지 점에 정사각형에 들어가는지 판단, 세번째 정사각형 완성
- k를 변경해가면서 수행 : O(nlogk)
- 추가 고려사항
- y최소/최대, x최소/최대에 따라 추가로 고려해야하는 경우가 나옴
- 총 8가지를 고려해봐야함
- y 최소에서 시작하는 경우
- x 최소, x 최소
- x 최소, x 최대
- x 최대, x 최소
- x 최대, x 최대
- y 최대에서 시작하는 경우
- x 최소, x 최소
- x 최소, x 최대
- x 최대, x 최소
- x 최대, x 최대
newbieski