Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

Si vous avez lu Lucky Luke lorsque vous étiez petit, vous savez sûrement que les indiens communiquent à l'aide de petits nuages de fumée. Les nuages de fumée se voient de loin (surtout dans les grandes plaines américaines), et en utilisant plusieurs faiseurs de nuages qui reproduisent les signaux qu'ils observent, un message peut parcourir des dizaines de kilomètres en très peu de temps. Quand on y pense, c'était un moyen de communication plutôt efficace (du temps où il fallait choisir entre de la fumée ou des pigeons).

En fait, le seul vrai problème avec les signaux de fumée, c'est le mauvais temps, qui réduit considérablement la visibilité des signaux. Vous êtes le chef de la tribu, et vous souhaitez prévoir précisement le nombre de membres de votre tribu que vous ne pourrez pas joindre les jours de mauvais temps.

Vous disposez d'un plan de la région (une carte 2D) qui indique la position exacte de tous les faiseurs de nuages de votre tribu, dont celui qui se trouve à côté de vous dans le camp principal, et à qui vous dictez les messages à transmettre.

Lorsqu'un faiseur de nuages voit un signal de fumée, il le réémet immédiatement, afin de transmettre le message à d'autres camps.

Grâce aux pouvoirs du grand Chamane de votre tribu, vous disposez de prédictions météo pour les jours qui viennent. Chaque prédiction est donnée sous la forme d'un nombre entier : la distance maximale à laquelle un signal de fumée pourra être vu ce jour là.

Votre objectif est de déterminer, pour chaque jour pour lequel vous disposez de ces prédictions, le nombre de faiseurs de nuages qui ne recevront pas vos messages ce jour là (directement ou indirectement).

Remarque : un faiseur de fumée se trouvant exactement à la distance maximale d'un deuxième, voit les signaux de celui-ci (et réciproquement).

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 32 000 ko.

Contraintes

  • 2 <= N <= 1 000, où N est le nombre de faiseurs de signaux de fumées.
  • -65 000 <= X,Y <= 65 000, où X et Y sont des coordonnées entières.
  • 0 <= D <= 200 000, où D est une distance de visibilité.
  • 0 <= M <= 10 000, où M est le nombre de jours pour lesquels vous disposez de prédictions météorologiques.

Remarque : dans 50% des tests, on aura N <= 100 et M <= 100.

Remarque : le faiseur de fumée correspondant au camp principal est le premier des faiseurs de fumée que l'on vous donne sur l'entrée standard.

Entrée

  • La première ligne contient un entier N, le nombre de faiseurs de fumée.
  • Les N lignes suivantes contiennent deux entiers chacune X et Y décrivant les coordonnées d'un faiseur de fumée.
  • La ligne suivante contient un entier M : le nombre de jours considérés.
  • Les M lignes suivantes contiennent chacune un entier : la distance Di de visibilité de chaque jour i.

Sortie

Vous devez afficher M lignes avec un entier chacune : pour chaque jour dans l'ordre de l'entrée, le nombre de faiseurs de nuages injoignables.

Exemple

entrée :

6
10 25
17 31
1 19
33 31
33 22
25 5
3
10
7
17

sortie :

4
5
1

Commentaires

L'image ci-dessous représente les positions des 6 faiseurs de nuages de l'exemple, numérotés de 1 à 6.

Le premier jour, le ciel est assez nuageux, et les signaux ne peuvent être vus que jusqu'à une distance de 10km. Seul le numéro 2 reçoit le message. Il le réémet, mais personne d'autre que le 1 ne peut voir ses signaux. Il reste donc 4 faiseurs de nuages qui ne reçoivent rien.

Le deuxième jour, le temps est mauvais, et on ne voit les signaux que jusqu'à une distance de 7km. Personne ne voit les signaux émis par le numéro 1. Cinq faiseurs de nuages n'ont donc rien reçu.

Le troisième jour, le ciel est dégagé, et la distance à laquel un signal peut être vu est de 17km. Le message émis par le faiseur de fumée 1 peut être vu directement par les numéros 2 et 3. Le numéro 4 peut voir le message retransmis par le numéro 2. Le numéro 5 voit alors le message retransmis par le 4. Le 3 et le 5 retransmettent aussi leur message, mais ce n'est pas suffisant pour qu'il soit vu par le faiseur de fumée 6. C'est le seul faiseur de nuages qui ne reçoit pas le message.

Vous devez être connecté pour résoudre cet exercice.

Vous devez être connecté(e) pour résoudre ce problème.

L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.

Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.

Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.

Une correction sera mise en ligne après la fin de l'épreuve.