목록MMRECT1 (1)

Software Engineering Note

최소, 최대 정사각형 찾기 1

문제: MMRECT1 / 구현 문제를 처음 보고 "좌표를 어떻게 표현해야 할까?" 하는 고민.. -10000 ~ 10000 범위를 모두 표현하기는 불가능해보인다. 점의 갯수가 50개 이하니까 입력된 점을 체크해보는 방식이 합리적으로 보인다. 정사각형의 특징을 이용하면 빨리 풀 수 있을 듯 해결전략 1. 시작점 하나를 선택2. x는 같은데 y좌표가 다른 점을 찾는다. 그리고 거리(=dist)를 구한다.3. y는 같으면서, x가 dist만큼 떨어진 점을 찾는다.4. 2에서 구한 점의 y 좌표와, 3에서 구한 점의 x 좌표를 값으로 갖는 점이 존재하는지 체크하고 최소/최대값 갱신 코드: https://github.com/xgate/algospot/blob/master/IMPL/MMRECT1.cpp
알고리즘/알고스팟 2014. 12. 27. 15:14
이전 Prev 1 Next 다음