시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB105473743.529%

문제

X축 위에 중심 좌표가 Ci이고 반지름이 Ri인 원이 N개 있다.

여기서 원을 몇 개를 지우면 모든 원이 서로 교차하지 않을까?

두 원이 접하는 경우는 교차하지 않는 것으로 생각한다.

원이 주어졌을 때, 모든 원이 서로 교차하지 않기 위해 지워야 하는 원의 최소 개수를 구하는 프로그램을 작성하시오.

입력

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

다음 N개의 줄에는 두 정수 Ci와 Ri가 주어진다. Ci는 i번째 원의 중심 좌표이고, Ri는 그 원의 반지름이다. (1 ≤ Ci, Ri ≤ 100) 

두 원이 반지름과 중심 좌표가 모두 같은 경우는 없다.

출력

첫째 줄에 원이 서로 교차하지 않기 위해 지워야 하는 원의 최소 개수를 출력한다.

예제 입력 1

6
2 1
5 1
6 1
1 2
3 2
4 3

예제 출력 1

2

예제 입력 2

7
40 30
25 15
35 5
70 20
60 30
60 10
80 10

예제 출력 2

2
W3sicHJvYmxlbV9pZCI6IjMxMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzZkMCIsImRlc2NyaXB0aW9uIjoiPHA+WFx1Y2Q5NSBcdWM3MDRcdWM1ZDAgXHVjOTExXHVjMmVjIFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBDPHN1Yj5pPFwvc3ViPlx1Yzc3NFx1YWNlMCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgUjxzdWI+aTxcL3N1Yj5cdWM3NzggXHVjNmQwXHVjNzc0IE5cdWFjMWMgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzg4YmM3ZjI1LTI3YTUtNDhiZS1iMTgxLWM0NGIyNmVlMjQ4YlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzY1cHg7IGhlaWdodDogMjM1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzExYyBcdWM2ZDBcdWM3NDQgXHViYTg3IFx1YWMxY1x1Yjk3YyBcdWM5YzBcdWM2YjBcdWJhNzQgXHViYWE4XHViNGUwIFx1YzZkMFx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVhZDUwXHVjYzI4XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NFx1YWU0Yz88XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzZkMFx1Yzc3NCBcdWM4MTFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmQwXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWM3NzQgXHVjMTFjXHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzljMFx1YzZjY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNmQwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZkMFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBDPHN1Yj5pPFwvc3ViPlx1YzY0MCBSPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEM8c3ViPmk8XC9zdWI+XHViMjk0IGlcdWJjODhcdWM5ZjggXHVjNmQwXHVjNzU4IFx1YzkxMVx1YzJlYyBcdWM4OGNcdWQ0NWNcdWM3NzRcdWFjZTAsIFI8c3ViPmk8XC9zdWI+XHViMjk0IFx1YWRmOCBcdWM2ZDBcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0XHVjNzc0XHViMmU0LiAoMSAmbGU7IEM8c3ViPmk8XC9zdWI+LCBSPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCkmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzZkMFx1Yzc3NCBcdWJjMThcdWM5YzBcdWI5ODRcdWFjZmMgXHVjOTExXHVjMmVjIFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2ZDBcdWM3NzQgXHVjMTFjXHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzljMFx1YzZjY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNmQwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMxMDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLUlVaTklDRSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIE4gY2lyY2xlcyBvbiB0aGUgY29vcmRpbmF0ZSBheGlzIGRlZmluZWQgYnkgY29vcmRpbmF0ZSBvZiB0aGUgY2VudGVyIEM8c3ViPmk8XC9zdWI+IGFuZCByYWRpdXMgUjxzdWI+aTxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvODhiYzdmMjUtMjdhNS00OGJlLWIxODEtYzQ0YjI2ZWUyNDhiXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAzNjVweDsgaGVpZ2h0OiAyMzVweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBjaXJjbGVzIHRoYXQgaGF2ZSB0byBiZSByZW1vdmVkIHN1Y2ggdGhhdCB0aGVyZSBpcyBubyBpbnRlcnNlY3RpbmcgcGFpciBvZiBjaXJjbGVzIGFtb25nIHRoZSByZW1haW5pbmcgY2lyY2xlcy4gUmVtYWluaW5nIGNpcmNsZXMgYXJlIGFsbG93ZWQgdG8gdG91Y2ggYXQgb25lIHBvaW50LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwKSwgbnVtYmVyIG9mIGNpcmNsZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbiB0d28gaW50ZWdlcnMgZWFjaCBDPHN1Yj5pPFwvc3ViPiBhbmQgUjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiwgUjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDApLCBjb29yZGluYXRlIG9mIHRoZSBjZW50ZXIgYW5kIHJhZGl1cyBvZiBlYWNoIGNpcmNsZS4gVHdvIGNpcmNsZXMgd2l0aCB0aGUgc2FtZSByYWRpdXMgd2lsbCBhbHdheXMgYmUgY2VudGVyZWQgYXQgZGlmZmVyZW50IGNvb3JkaW5hdGUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBpbnRlZ2VyLCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNpcmNsZXMgdGhhdCBoYXZlIHRvIGJlIHJlbW92ZWQgc3VjaCB0aGF0IG5vIHBhaXIgb2YgcmVtYWluaW5nIGNpcmNsZXMgaW50ZXJzZWN0cy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Q2xhcmlmaWNhdGlvbiBmb3IgdGhlIGZpcnN0IHNhbXBsZTogSWYgd2UgcmVtb3ZlICg1IDEpIGFuZCAoMSAyKSwgdGhlIHJlbWFpbmluZyBjaXJjbGVzIGRvIG5vdCBpbnRlcnNlY3QuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d