최소, 최대 정사각형 찾기 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