시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 26 13 11 61.111%

문제

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
W3sicHJvYmxlbV9pZCI6IjMxMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzZkMCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0WFx1Y2Q5NSBcdWM3MDRcdWM1ZDAgXHVjOTExXHVjMmVjIFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBDPHN1Yj5pPFwvc3ViPlx1Yzc3NFx1YWNlMCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgUjxzdWI+aTxcL3N1Yj5cdWM3NzggXHVjNmQwXHVjNzc0IE5cdWFjMWMgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL29uZS5wbmdcIiBzdHlsZT1cIndpZHRoOiA0MThweDsgaGVpZ2h0OiAyNDJweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNWVjXHVhZTMwXHVjMTFjIFx1YzZkMFx1Yzc0NCBcdWJhODcgXHVhYzFjXHViOTdjIFx1YzljMFx1YzZiMFx1YmE3NCBcdWJhYThcdWI0ZTAgXHVjNmQwXHVjNzc0IFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0XHVhZTRjPzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHVjNmQwXHVjNzc0IFx1YzgxMVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVhZDUwXHVjYzI4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjODNcdWM3M2NcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2ZDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1YzZkMFx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVhZDUwXHVjYzI4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjOWMwXHVjNmNjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM2ZDBcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZkMFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEsMDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBDPHN1Yj5pPFwvc3ViPlx1YzY0MCBSPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEM8c3ViPmk8XC9zdWI+XHViMjk0IGlcdWJjODhcdWM5ZjggXHVjNmQwXHVjNzU4IFx1YzkxMVx1YzJlYyBcdWM4OGNcdWQ0NWNcdWM3NzRcdWFjZTAsIFI8c3ViPmk8XC9zdWI+XHViMjk0IFx1YWRmOCBcdWM2ZDBcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0XHVjNzc0XHViMmU0LiAoMSAmbGU7IEM8c3ViPmk8XC9zdWI+LCBSPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCkmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDUwIFx1YzZkMFx1Yzc3NCBcdWJjMThcdWM5YzBcdWI5ODRcdWFjZmMgXHVjOTExXHVjMmVjIFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2ZDBcdWM3NzQgXHVjMTFjXHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzljMFx1YzZjY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNmQwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTAyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS1JVWk5JQ0UiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBOIGNpcmNsZXMgb24gdGhlIGNvb3JkaW5hdGUgYXhpcyBkZWZpbmVkIGJ5IGNvb3JkaW5hdGUgb2YgdGhlIGNlbnRlciBDPHN1Yj5pPFwvc3ViPiBhbmQgcmFkaXVzIFI8c3ViPmk8XC9zdWI+LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL29uZS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDJweDsgd2lkdGg6NDE4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBjaXJjbGVzIHRoYXQgaGF2ZSB0byBiZSByZW1vdmVkIHN1Y2ggdGhhdCB0aGVyZSBpcyBubyBpbnRlcnNlY3RpbmcgcGFpciBvZiBjaXJjbGVzIGFtb25nIHRoZSByZW1haW5pbmcgY2lyY2xlcy4gUmVtYWluaW5nIGNpcmNsZXMgYXJlIGFsbG93ZWQgdG8gdG91Y2ggYXQgb25lIHBvaW50LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwKSwgbnVtYmVyIG9mIGNpcmNsZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbiB0d28gaW50ZWdlcnMgZWFjaCBDPHN1Yj5pPFwvc3ViPiBhbmQgUjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBDPHN1Yj5pPFwvc3ViPiwgUjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDApLCBjb29yZGluYXRlIG9mIHRoZSBjZW50ZXIgYW5kIHJhZGl1cyBvZiBlYWNoIGNpcmNsZS4gVHdvIGNpcmNsZXMgd2l0aCB0aGUgc2FtZSByYWRpdXMgd2lsbCBhbHdheXMgYmUgY2VudGVyZWQgYXQgZGlmZmVyZW50IGNvb3JkaW5hdGUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBpbnRlZ2VyLCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNpcmNsZXMgdGhhdCBoYXZlIHRvIGJlIHJlbW92ZWQgc3VjaCB0aGF0IG5vIHBhaXIgb2YgcmVtYWluaW5nIGNpcmNsZXMgaW50ZXJzZWN0cy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=