레이팅 미적용소 베시는 농장의 자기 목초지에서 지평선 위의 산맥을 멋지게 바라볼 수 있다. 산맥에는 \(N\)개의 산이 있다 (\(1 \leq N \leq 10^5\)). 베시의 시야를 \(xy\) 평면으로 생각하면, 각 산은 밑변이 \(x\)축 위에 놓인 삼각형이다. 산의 양쪽 빗면은 모두 밑변과 45도를 이루므로, 산의 봉우리는 직각을 이룬다. 따라서 산 \(i\)는 봉우리의 위치 \((x_i, y_i)\)로 정확하게 표현된다. 봉우리의 위치가 정확히 같은 두 산은 없다.
베시는 산을 전부 세어 보려 하지만, 산들의 색이 대체로 비슷해서 어떤 산의 봉우리가 다른 산의 삼각형 모양의 경계 위나 내부에 있으면 그 산을 볼 수 없다.
베시가 볼 수 있는 서로 다른 봉우리의 개수, 즉 산의 개수를 구하여라.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 나머지 \(N\)개의 줄에는 각각 산 하나의 봉우리 위치를 나타내는 \(x_i\) (\(0 \leq x_i \leq 10^9\))와 \(y_i\) (\(1 \leq y_i \leq 10^9\))가 주어진다.
베시가 구별할 수 있는 산의 개수를 출력한다.
mountains.in · 출력을 쓸 파일 mountains.out3
4 6
7 2
2 52In this example, Bessie can see the first and last mountain. The second
mountain is obscured by the first.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > January > Silver