Extension Stratégique – Qualification 2023

Niveau 6

Énoncé

La machine est dorénavant prête au décollage ! Mais avant cela, il faut planifier le voyage, dans la plus grande des précautions.

Pour pouvoir se déplacer efficacement, il existe des points de contrôle permettant un mouvement d'une vitesse proche de la vitesse de la lumière ! Mais ces déplacements pouvant être dangereux, une zone de sécurité a été construite, contenant tous les tunnels entre les points de contrôle.

Pour contribuer à la recherche spatio-temporelle, Augustin planifie la construction d'un nouveau point de contrôle...

Il existe aujourd'hui $N + 1$ points de contrôle, dont leur position est définie par deux coordonnées dans le plan spatio-temporel. Votre machine se situe au premier point de contrôle, de coordonnées $(0, 0)$. Vous connaissez la position des $N$ autres points de contrôle.

Chaque paire de points de contrôle est reliée par un tunnel en ligne droite dans le plan spatio-temporel. Afin de s'assurer de la sécurité des déplacements entre les points de contrôle, il existe une zone de sécurité, représentée dans le plan spatio-temporel par un polygone d'aire minimale, contenant la totalité des tunnels.

Augustin planifie la construction d'un nouveau point de contrôle dans le plan spatio-temporel. La zone de sécurité sera adaptée pour y intégrer le nouveau point de contrôle ainsi que tous les tunnels en direction de celui-ci, tout en restant un polygone et en gardant une aire minimale.

Attention cependant, vous ne disposez d'aucune information concernant ce qui se passe au delà d'une distance D de votre machine temporelle. Au delà de cette distance, c'est un grand flou que personne n'a encore jamais exploré ! Autrement dit, l'espace-temps connu forme un cercle de rayon D centré sur votre machine dans le plan spatio-temporel. Il est hors de question de construire un point de contrôle en dehors de cette zone ! Tous les points de contrôle actuels sont d'ailleurs situés dans l'espace-temps connu.

Aidez Augustin à déterminer quel serait le nombre minimal d'arêtes de la zone de sécurité après la construction de votre point de contrôle.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : D, le rayon de l'espace-temps connu.
  • Sur la ligne suivante, un entier : N, le nombre de points de contrôle existants (sans compter celui sur lequel vous vous situez actuellement).
  • Sur les lignes suivantes, une liste de N éléments : points de contrôle, la liste des coordonnées des points de contrôle existants.
    • Une ligne par élément de la liste : séparés par des espaces, un entier x (la coordonnée x dans le plan spatio-temporel), et un entier y (la coordonnée y dans le plan spatio-temporel).

Sortie

Afficher, sur une ligne, le nombre d'arêtes minimal de la zone de sécurité après la création d'un nouveau point de contrôle dans l'espace-temps connu.

Contraintes

  • $1 \le D \le 10^9$
  • $1 \le N \le 4$ Tous les points de contrôle sont situés à des endroits strictement différents. Autrement dit:
  • $(x_i, y_i) \neq (0, 0)$ pour tout $0 \le i < N$
  • $(x_i, y_i) \neq (x_j, y_j)$ pour tout $0 \le i, j < N, i \neq j$

Contraintes de performance

  • $1 \le N \le 100\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
3000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
3
1 0
2 1
2 -1
Exemple de sortie
3
Commentaire

Voici la configuration actuelle :

Configuration initiale

Actuellement, la zone de sécurité forme un triangle. Il est possible d'ajouter le nouveau point de contrôle en (-1.5, 0.5), et la zone de sécurité restera toujours un triangle. C'est pourquoi la réponse est 3.

Exemple de solution optimale

Notez qu'il aurait aussi été possible de placer le nouveau point de contrôle en (-3, 0), en bordure de l'espace-temps connu; ou en (1.5, 0.5), à l'intérieur de la zone de sécurité; ou même en (2.5, -1.5), et la zone de sécurité aurait également été un triangle. Toutes ces solutions font partie des solutions optimales de cette configuration.

En revanche, si le nouveau point de contrôle avait été placé en (0, 1) par exemple, alors la zone de sécurité aurait été un quadrilatère.

Exemple d'entrée
4
4
0 2
1 2
2 0
2 1
Exemple de sortie
4
Commentaire

Ici, il est par exemple possible de rajouter un nouveau point de contrôle en (2.5, 2.5).

Exemple de solution optimale

Dans ce cas précis, la zone de sécurité formera un quadrilatère, dont les coins se situeraient aux coordonnées (0, 0), (0, 2), (2.5, 2.5), (2, 0). Il n'est ici pas possible de faire en sorte que la zone de sécurité forme un triangle, la solution optimale est donc un quadrilatère.

Exemple d'entrée
1
2
-1 0
1 0
Exemple de sortie
2
Commentaire

Ici, il est par exemple possible d'ajouter un nouveau point de contrôle en (0.5, 0).

Exemple de solution optimale

La zone de sécurité sera alors un segment, soit un polygone à deux côtés.