BOJ 27537 - Advertisement 2

image.png

(Xi,Ei)(X_i, E_i) 를 좌표로 나타내고 좌우로 45°45\degree 씩 아래로 내려보자.

i→ji \to j 에게 전파할 수 있다는 것은 ii 의 직각이등변삼각형이 jj의 것을 완전히 포함한다는 것과 동치이다.

따라서 (Xi−Ei,Xi+Ei)(X_i-E_i, X_i+E_i) 를 삼각형의 시작과 끝으로 두고, 시작에 대해선 오름차순, 끝에 대해선 내림차순으로 정렬하여 스택을 활용하여 풀어준다.

Tags:

Categories:

Updated:

Comments

You may also enjoy