{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Supongamos que la costa es una línea recta infinita. La tierra está en un lado de la costa, el mar en el otro. Cada pequeña isla es un punto ubicado en el lado del mar. Y cualquier instalación de radar, ubicada en la costa, solo puede cubrir una distancia d, por lo que una isla en el mar puede ser cubierta por una instalación de radar si la distancia entre ellos es a lo sumo d.\n\nUtilizamos un sistema de coordenadas cartesianas, definiendo la costa como el eje x. El lado del mar está por encima del eje x y el lado de la tierra por debajo. Dada la posición de cada isla en el mar, y dada la distancia de cobertura de la instalación de radar, tu tarea es escribir un programa para encontrar el número mínimo de instalaciones de radar necesarias para cubrir todas las islas. Ten en cuenta que la posición de una isla se representa por sus coordenadas x-y.\n\u003cbr\u003e\n\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/f6ffe515205096387436c13c7449b0ed?v\u003d1706083009\"\u003e\nFigura: Un ejemplo de entrada de instalaciones de radar\u003c/center\u003e"}},{"title":"Entrada","value":{"format":"HTML","content":"La entrada consiste en varios casos de prueba. La primera línea de cada caso contiene dos enteros n (1\u0026lt;\u003dn\u0026lt;\u003d1000) y d, donde n es el número de islas en el mar y d es la distancia de cobertura de la instalación de radar. A esto le siguen n líneas, cada una conteniendo dos enteros que representan las coordenadas de la posición de cada isla. Luego sigue una línea en blanco para separar los casos.\n\nLa entrada termina con una línea que contiene un par de ceros."}},{"title":"Salida","value":{"format":"HTML","content":"Para cada caso de prueba, imprime una línea que consista en el número del caso seguido del número mínimo de instalaciones de radar necesarias. \"-1\" significa que no hay solución para ese caso."}},{"title":"Ejemplo","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\r\n1 2\r\n-3 1\r\n2 1\r\n\r\n1 2\r\n0 2\r\n\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2\r\nCase 2: 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}