산맥

면접 대비

시간 제한2초메모리 제한512 MB

요약
밑변이 x축에 놓인 45도 직각삼각형 산들이 있을 때, 다른 산의 삼각형 안에 들어가지 않는 봉우리의 수를 센다.
난이도

보통10점 중 5점

유형
기하, 정렬, 그리디, 구현
정답자
아직 제출이 없습니다

문제

농장의 목초지에 있는 소 베시는 지평선 너머의 산맥을 멋지게 바라볼 수 있다. 산맥에는 NN개의 산이 있다 (1≤N≤1051 \leq N \leq 10^5). 베시의 시야를 xyxy 평면이라고 생각하면, 각 산은 밑변이 xx축에 놓인 삼각형이다. 산의 두 변은 모두 밑변과 45도 각도를 이루므로, 산의 꼭대기는 직각을 이룬다. 따라서 ii번째 산은 꼭대기의 위치 (x_i,y_i)(x\_i, y\_i)로 정확히 설명된다. 두 산의 꼭대기 위치가 완전히 같은 경우는 없다.

베시는 모든 산의 개수를 세려고 하지만, 산들이 모두 비슷한 색이라서 어떤 산의 꼭대기가 다른 산의 삼각형 모양 위에 있거나 그 안에 있으면 그 산을 볼 수 없다.

베시가 볼 수 있는 서로 다른 꼭대기, 즉 산의 개수를 구하시오.

입력

첫째 줄에 NN이 주어진다. 그다음 NN개의 줄에 각각 한 산의 꼭대기 위치를 나타내는 x_ix\_i (0≤x_i≤1090 \leq x\_i \leq 10^9)와 y_iy\_i (1≤y_i≤1091 \leq y\_i \leq 10^9)가 주어진다.

출력

베시가 구별할 수 있는 산의 개수를 출력하시오.

힌트

이 예에서 베시는 첫 번째 산과 마지막 산을 볼 수 있다. 두 번째 산은 첫 번째 산에 가려진다.

예제1

  1. 예제 1

    입력
    3
    4 6
    7 2
    2 5
    
    예상 출력
    2