La ACM (Association for Computing Machinery), organiza todos los años un concurso de programación orientado a jóvenes universitarios de todoel mundo. El concurso está dividido en varias fases, desde una primeraregional, nacional, europea y mundial.
¿Cómo es el concurso?. Se participa por grupos de trespersonas, los cuales disponen de un solo ordenador para resolver cada uno delos 10 problemas que se reparten al principio, para ello se disponen de 6horas.
¿Cómo son los problemas que hay solucionar?. Los hay de muy diversa índole, lo que si es cierto es que suelen ser bastante complejos yno siempre la primera solución suele ser la buena, ya que según queproblemas están limitados en tiempo o en el uso de memoria, por lo que hayque buscar una solución optima lo más rápidamente posible. A continuación pondrá un problema ejemplo de los que salen en el concurso (por cierto,todos los problemas están en inglés).
Count wireless Links
Wireless networking is our future, provided at least some connectionsexist!
More precisely, N nodes of a radio network are distributed in a L x H area.Two nodes may communicate if their euclidean distance is strictly less thanR , the radio range. We then say that there exists a wireless link betweenthose two nodes. Of course, we do not consider that a node has a link withitself.
Problem
Write a program that, given a description of the positions of the nodes,outputs the number of wireless links in the network.
Input specification
The positions ( x , y ) of the nodes are integers in the ranges 0=x < Land 0= y < H . The first line of the input consists of the four integersL, H ,R and N , with 0 < L = 5*10 6 , 0 <H = 5*10 6 , 0 < R = 30000, 0< N = 300000.
Output specification
The output consists of a single line containing the number of wireless links in the network.
Sample Input
30 20 11 60 00 1010 010 1020 020 10Sample Output
7
Enlaces
