Circulos


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Hay N círculos sobre los ejes de coordenadas definidos por la coordenada del centro C_i y el radio R_i.

Descripcion

Escriba un programa que determine el número más pequeño de círculos que tienen que ser removidos tal que no exista pares de círculos que se intersectan entre los círculos restantes. A los círculos restantes se les permite tocarse en un punto.

Entrada

La primera línea de la entrada contiene un entero N (1 \le N \le 1000), el número de círculos. Las próximas N líneas contienen dos enteros cada una C_i y R_i  (1 \le Ci, Ri  \le 100), las coordenadas del centro y del radio de cada circulo. Dos círculos con el mismo radio siempre estarán centrados en diferente coordenada..

Salida

La salida contiene un entero, el número menor de círculos que deben ser quitados de modo que ningún par de círculos de los restantes se intersecten.

Ejemplo # 1 de Entrada

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

Ejemplo # 1 de Salida

2

Explicación del Primer ejemplo Si removemos (5 1) y (1 2), los círculos restantes no se intersectan.

Ejemplo # 2 de Entrada

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

Ejemplo # 2 de Salida

2

Comments

There are no comments at the moment.