시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 59 26 20 44.444%

문제

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+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLUlVaTklDRSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIE4gY2lyY2xlcyBvbiB0aGUgY29vcmRpbmF0ZSBheGlzIGRlZmluZWQgYnkgY29vcmRpbmF0ZSBvZiB0aGUgY2VudGVyIEM8c3ViPmk8XC9zdWI+IGFuZCByYWRpdXMgUjxzdWI+aTxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvb25lLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI0MnB4OyB3aWR0aDo0MThweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGRldGVybWluZSB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNpcmNsZXMgdGhhdCBoYXZlIHRvIGJlIHJlbW92ZWQgc3VjaCB0aGF0IHRoZXJlIGlzIG5vIGludGVyc2VjdGluZyBwYWlyIG9mIGNpcmNsZXMgYW1vbmcgdGhlIHJlbWFpbmluZyBjaXJjbGVzLiBSZW1haW5pbmcgY2lyY2xlcyBhcmUgYWxsb3dlZCB0byB0b3VjaCBhdCBvbmUgcG9pbnQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDApLCBudW1iZXIgb2YgY2lyY2xlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBjb250YWluIHR3byBpbnRlZ2VycyBlYWNoIEM8c3ViPmk8XC9zdWI+IGFuZCBSPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IEM8c3ViPmk8XC9zdWI+LCBSPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCksIGNvb3JkaW5hdGUgb2YgdGhlIGNlbnRlciBhbmQgcmFkaXVzIG9mIGVhY2ggY2lyY2xlLiBUd28gY2lyY2xlcyB3aXRoIHRoZSBzYW1lIHJhZGl1cyB3aWxsIGFsd2F5cyBiZSBjZW50ZXJlZCBhdCBkaWZmZXJlbnQgY29vcmRpbmF0ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGludGVnZXIsIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgY2lyY2xlcyB0aGF0IGhhdmUgdG8gYmUgcmVtb3ZlZCBzdWNoIHRoYXQgbm8gcGFpciBvZiByZW1haW5pbmcgY2lyY2xlcyBpbnRlcnNlY3RzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d