티스토리 뷰

ICPC/2014 대전

I. Three Squares

전명우 2014.11.10 01:24

2차원 평면에 점들이 $N$개 주어졌을 때, 동일한 크기인 정사각형 세 개로 모든 점들을 덮을 때 가능한 정사각형의 최소 크기를 구하는 문제다.


주어진 $N$개의 점을 포함하는 최소 직사각형을 생각하자. 서로 다른 점이 4개 이상일 때 아래와 같은 명제가 성립한다.


최소 크기의 정사각형 세 개로 모든 점을 덮을 때, 그 정사각형 중 하나는 직사각형의 네 꼭지점 중 하나의 점을 꼭지점으로 한다.


비슷한 상황으로 최소 크기의 정사각형 두 개로, 서로 다른 점 3개 이상을 모두 덮는다고 할 때, 아래와 같은 명제가 성립한다.


최소 크기의 정사각형 두 개로 모든 점을 덮을 때, 두 정사각형은 서로 대각으로 마주보는 두 꼭지점을 꼭지점으로 한다.


이분 검색으로 정사각형의 크기 $s$를 정하고 모든 점을 덮을 수 있는지 $O(N)$ 만에 확인할 수 있다. 따라서, 총 시간복잡도는 $O(N \lg X)$가 된다. 여기서 $X$는 좌표계의 크기다.


코드 보기


'ICPC > 2014 대전' 카테고리의 다른 글

K. Travel Card  (2) 2014.11.10
J. Tours  (0) 2014.11.10
I. Three Squares  (0) 2014.11.10
H. String Transformation  (0) 2014.11.10
G. Road Repair  (0) 2014.11.10
F. Permutation Cycles  (0) 2014.11.09
댓글
댓글쓰기 폼