아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

원 영역

시간 제한1초메모리 제한256 MB

요약
중심이 x축 위에 있고 서로 교차하지 않는 N개 원이 평면을 나누는 영역 개수를 구합니다.
난이도

보통10점 중 7점

유형
스택, 정렬, 유니온 파인드, 수학
정답자
아직 제출이 없습니다

문제

x축 위에 원이 NN개 놓여 있다. 모든 원의 중심은 x축 위에 있고, 원끼리 서로 교차하지 않는다. 다만 접할 수는 있다.

이 원들이 평면을 몇 개의 영역으로 나누는지 구하는 프로그램을 작성하시오.

영역은 점의 집합이고, 그 안의 두 점은 어떤 원과도 만나지 않는 연속인 곡선으로 이을 수 있어야 한다. 원 바깥으로 무한히 뻗은 부분도 영역 하나로 센다.

입력

첫째 줄에 원의 개수 NN (1≤N≤300 0001 \le N \le 300\,000)이 주어진다.

다음 NN개 줄에는 원의 정보가 정수 xix_i와 rir_i로 한 줄에 하나씩 주어진다. xix_i는 원의 중심의 x좌표이고, rir_i는 반지름이다. (−109≤xi≤109-10^9 \le x_i \le 10^9, 1≤ri≤1091 \le r_i \le 10^9)

같은 원이 두 번 주어지는 경우는 없다.

출력

첫째 줄에 원이 만드는 영역의 개수를 출력한다.

예제3

  1. 예제 1

    입력
    2
    1 3
    5 1
    
    예상 출력
    3
    
  2. 예제 2

    입력
    3
    2 2
    1 1
    3 1
    
    예상 출력
    5
    
  3. 예제 3

    입력
    4
    7 5
    -9 11
    11 9
    0 20
    
    예상 출력
    6