블로그 이사 중입니다 >> gumgood.github.io

C++11 flag

C++11 전처리를 통해 i번째 좌표의 상하좌우에 몇 번째 좌표가 있는지 저장해둔다. O(NlogN) 그 정보를 바탕으로 외계인의 명령을 따라간다. O(M) O(NlogN + M) 전처리의 아이디어는 다음과 같다. 1) X좌표 기준으로 sorting했을 때 연속된 두 점의 x좌표가 같다면 두 점은 상하관계에 있다 2) y좌표 기준으로 sorting했을 때 연속된 두 점의 y좌표가 같다면 두 점은 좌우관계에 있다