[BOJ 5419]

문제 바로가기 : https://www.acmicpc.net/problem/5419
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

문제는 꽤나 간단해 보이지만, 아이디어를 세우기가 까다롭다고 생각이 들은 문제였다.
아이디어 설명은 kks227님의 글에 더 자세하게 되어있다! 참고 권장!

북서풍은 북서쪽에서 불어오는 바람으로 좌표평면에서 원점을 잡으면 4사분면이 영향권이라고 보면 된다.
섬들의 좌표를 입력받고 각 좌표가 북서풍이 시작되는 지점일 때 영향을 받는 섬들의 개수를 합하면 된다.
말이 북서풍이지 어느 방향으로 해도 일관성있는 방향으로만 진행하면 상관없다.
x좌표가 제일 작은 섬부터 제일 큰 섬까지 이동하고, 만약 x좌표가 같다면 y좌표가 더 큰 섬으로 설정했다.

y좌표의 경우 좌표 범위가 어마어마하다. 음수는 인덱스로 쓸 수 없을 뿐더러 섬의 개수가 그렇게 크지 않다.
때문에 정렬해서 인덱스로 쓸 수 있도록 y값을 고쳐줘야 한다. 이후에는 왼쪽부터 처리될 수 있도록 오름차순으로 정렬한다.
마지막은 쿼리를 이용해서 처리하면 된다.