시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB107536325937.536%

문제

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
W3sicHJvYmxlbV9pZCI6IjEwMDAwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNmQwIFx1YzYwMVx1YzVlZCIsImRlc2NyaXB0aW9uIjoiPHA+eFx1Y2Q5NSBcdWM3MDRcdWM1ZDAgXHVjNmQwXHVjNzc0IE5cdWFjMWMgXHVjNzg4XHViMmU0LiBcdWM2ZDBcdWM3NDAgXHVjMTFjXHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjODExXHVkNTYwIFx1YzIxOFx1YjI5NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZkMFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzBcdWIyOTQgXHVjNjAxXHVjNWVkXHVjNzc0IFx1YmE4NyBcdWFjMWNcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzYwMVx1YzVlZFx1Yzc0MCBcdWM4MTBcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzNjXHViODVjIFx1YmFhOFx1YjRlMCBcdWI0NTAgXHVjODEwXHVjNzQwIFx1YzZkMFx1Yzc0NCBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzVmMFx1YzE4ZFx1YjQxOFx1YjI5NCBcdWFjZTFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDIwIFx1YzIxOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2MzNjBkYTk5LTg0NWYtNGZkYi1iMWY2LTYwYjgwOWVmNjQwYlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMjAxcHg7IGhlaWdodDogMjAxcHg7XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZkMFx1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDMwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWM2ZDBcdWM3NTggXHVjODE1XHViY2Y0IHg8c3ViPmk8XC9zdWI+XHVjNjQwIHI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIHg8c3ViPmk8XC9zdWI+XHViMjk0IFx1YzZkMFx1Yzc1OCBcdWM5MTFcdWMyZWMgXHVjODhjXHVkNDVjXHVjNzc0XHViYTcwLCByPHN1Yj5pPFwvc3ViPlx1YjI5NCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzRcdWIyZTQuJm5ic3A7KC0xMDxzdXA+OTxcL3N1cD4gJmxlOyB4PHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IHI8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzZkMFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjNzIwXHVjNzdjXHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNmQwXHVjNzNjXHViODVjIFx1Yzc3OFx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzBcdWIyOTQgXHVjNjAxXHVjNWVkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTAwMDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLUlVcdTAxN2ROSUNFIiwiZGVzY3JpcHRpb24iOiI8cD5FbmpveWluZyBhIGNhc3VhbCBhZnRlcm5vb24gd2FsayBpbiB0aGUgY29vcmRpbmF0ZSBzeXN0ZW0sIGxpdHRsZSBMdWthIGhhcyBlbmNvdW50ZXJlZCBOIHVuaXF1ZSBjaXJjbGVzIHdpdGggaXRzIGNlbnRlcnMgbHlpbmcgb24gdGhlIHgtYXhpcy4gVGhlIGNpcmNsZXMgZG8gbm90IGludGVyc2VjdCwgYnV0IHRoZXkgY2FuIHRvdWNoIChmcm9tIHRoZSBpbnNpZGUgYW5kIHRoZSBvdXRzaWRlKS4gRmFzY2luYXRlZCB3aXRoIGNpcmNsZXMsIEx1a2Egd29uZGVyZWQgaG93IG1hbnkgcmVnaW9ucyB0aGUgY2lyY2xlcyBkaXZpZGUgdGhlIHBsYW5lIGludG8uIE9mIGNvdXJzZSwgeW91IGFyZSBnb2luZyB0byBoZWxwIGhpbSBhbnN3ZXIgdGhpcyBxdWVzdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSByZWdpb24gaXMgYSBzZXQgb2YgcG9pbnRzIHN1Y2ggdGhhdCBlYWNoIHR3byBwb2ludHMgY2FuIGJlIGNvbm5lY3RlZCB3aXRoIGEgY29udGludW91cyBjdXJ2ZSwgd2l0aG91dCBjdXR0aW5nIHRocm91Z2ggYW55IG9mIHRoZSBjaXJjbGVzLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2MzNjBkYTk5LTg0NWYtNGZkYi1iMWY2LTYwYjgwOWVmNjQwYlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMjAxcHg7IGhlaWdodDogMjAxcHg7XCIgXC8+Jm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPk9uZSBvZiB0aGUgcG9zc2libGUgbGF5b3V0cyBvZiBjaXJjbGVzPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGNpcmNsZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB4PHN1Yj5pPFwvc3ViPiBhbmQgcjxzdWI+aTxcL3N1Yj4gKC0xMDxzdXA+OTxcL3N1cD4gJmxlOyB4PHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IHI8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgdGhlIG51bWJlciB4PHN1Yj5pPFwvc3ViPiByZXByZXNlbnRpbmcgdGhlIHggY29vcmRpbmF0ZSBvZiB0aGUgaTxzdXA+dGg8XC9zdXA+IGNpcmNsZSBhbmQgdGhlIG51bWJlciByPHN1Yj5pPFwvc3ViPiByZXByZXNlbnRpbmcgdGhlIHJhZGl1cyBvZiB0aGUgaTxzdXA+dGg8XC9zdXA+IGNpcmNsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWxsIHRoZSBjaXJjbGVzIGluIHRoZSBpbnB1dCB3aWxsIGJlIHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBudW1iZXIgZnJvbSB0aGUgdGFzay4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIHRoaXJkIGV4YW1wbGU6IFRoZSBleGFtcGxlIGNvcnJlc3BvbmRzIHRvIHRoZSBpbWFnZSBpbiB0aGUgdGFzayBzdGF0ZW1lbnQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #6 4번

  • 데이터를 추가한 사람: Acka
  • 문제를 번역한 사람: baekjoon