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

문제: MMRECT2 / 구현

MMRECT1 문제랑 똑같은데 점의 갯수가 최대 20,000 개까지 입력될 수 있다.

MMRECT1 처럼알고리즘으로 풀면 TLE를 면치 못하겠다.

해서, 메모리를 좀 이용하기로 했다.

해결전략

1. x좌표가 같은 점들을 한 곳에 모아놓는다. (map<key=x좌표, value=좌표 리스트>)

2. 루프를 돌면서 입력된 점을 하나씩 꺼내고, map에서 좌표리스트를 꺼낸다.

3. 좌표리스트를 돌면서 다음을 수행 (정사각형의 조건을 생각해보자)

- x좌표는 어차피 같으니까 y 차이를 구한다. (=dist)

- 좌표 p1, p2에서 같은 방향으로 dist만큼 떨어진 점이 있는지 찾아본다.

- 예를 들어, y 값이 2 차이나면 두 점의 왼쪽에 2만큼 떨어진 곳에 점이 있거나, 오른쪽으로 2만큼 떨어진 곳에 점이 있어야한다.

4. 정사각형 조건에 맞으면 최소,최대 값 갱신

결과적으로 필요한 좌표들만 검사하는 전략을 취했다.

코드: https://github.com/xgate/algospot/blob/master/IMPL/MMRECT2.cpp