[BOJ 10000] 원 영역

View as PDF

Submit solution

Points: 4
Time limit: 1.0s
Memory limit: 256M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다.

원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오.

영역은 점의 집합으로 모든 두 점은 원을 교차하지 않는 연속되는 곡선으로 연결될 수 있어야 한다.

입력 형식

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

다음 N개 줄에는 각 원의 정보 xi와 ri가 정수로 주어진다. xi는 원의 중심 좌표이며, ri는 반지름이다. (-109 ≤ xi ≤ 109, 1 ≤ ri ≤ 109)

입력으로 주어지는 원은 항상 유일하다.

출력 형식

첫째 줄에 원으로 인해서 만들어지는 영역의 개수를 출력한다.

예제 입력 1

2
1 3
5 1

예제 출력 1

3

예제 입력 2

3
2 2
1 1
3 1

예제 출력 2

5

예제 입력 3

4
7 5
-9 11
11 9
0 20

예제 출력 3

6

Comments

There are no comments at the moment.