BOJ 27537 - Advertisement 2

BOJ 27537 - Advertisement 2

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

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

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