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]
Vous avez décidé de profiter du beau temps pour faire du camping avec vos amis. Après une bonne journée de pêche, suivie d'un bon repas autour d'un feu de bois au cours duquel vous avez épuisé tout votre répertoire de chansons, vous avez décidé de vous détendre en regardant les étoiles. Malheureusement, vous n'y connaissez rien aux diverses constellations.

Pour vous, les étoiles ne forment pas de magnifiques créatures ou personnages, ni même la moindre casserole. Vous avez toujours trouvé cela absurde d'apprendre par coeur les noms et positions des diverses constellations. Après tout, en cherchant bien, il est possible de trouver n'importe-quelle forme en reliant des groupes d'étoiles, tout est une question d'imagination. Vous décidez donc de rechercher vos propres formes dans le ciel.

Pour pimenter un peu les choses, vous proposez un petit concours à vos amis : le but est de trouver la plus grande flèche possible dans le ciel étoilé. Tous les moyens sont permis dans ce concours et alors que vos amis regardent tous au dessus d'eux, vous sortez discrètement votre appareil photo numérique et votre ordinateur portable, afin de vous assurer la victoire.

Vous devez écrire un programme qui trouve la plus grande flèche composée de trois étoiles exactement. Votre flèche doit être dirigée vers le haut, et les deux étoiles du côté gauche et droit de la flèche doivent se trouver exactement à la même hauteur. L'étoile qui forme la pointe de la flèche doit avoir son abscisse située strictement entre celle des deux autres et son ordonnée doit être strictement au dessus des deux autres.

Pour finir, la largeur de la flèche doit être plus petite ou égale à sa hauteur. Notez que la largeur de la flèche est définie comme étant la différence entre l'abscisse de l'étoile la plus à gauche et celle de l'étoile la plus à droite. La hauteur de la flèche est définie comme étant la différence entre l'ordonnée de la pointe de la flèche et celle des deux étoiles en dessous.

Ainsi, si les trois étoiles qui forment la flèche sont aux coordonnées (X1,Y1), (X2,Y2) et X3,Y3), on doit avoir X1 < X2 < X3 et Y2 < Y1 = Y3. La largeur de la flèche est X3-X1 et la hauteur de la flèche est Y1-Y2 et on doit donc avoir X3-X1 <= Y1-Y2. Le diagramme suivant illustre quelques flèches valides et invalides.

Flèches validesFlèches invalides

La taille d'une flèche est définie comme étant sa largeur plus sa hauteur. Lorsque vous cherchez la flèche la plus grande, vous recherchez donc la flèche dont la hauteur plus la largeur est la plus grande possible.

Limites de temps et de mémoire (Python)

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

Contraintes

  • 3 <= N <= 2000, où N est le nombre d'etoiles visibles dans le ciel.
  • 0 <= X, Y <= 1,000,000
  • , où X, Y sont les coordonnées d'une étoile.

Entrée

Votre programme doit lire directement sur l'entrée standard. La première ligne de l'entrée contient un entier : N, le nombre d'étoiles visibles dans le ciel.

Chacune des N lignes suivantes décrit une étoile et contient deux entiers positifs séparés par un espace : les coordonnées X et Y de l'étoile. On vous garantit qu'il n'y a pas deux étoiles à la même position dans le ciel.

Sortie

Votre programme doit écrire directement sur la sortie standard. Vous devez écrire un entier : la taille de la flèche la plus grande (i.e., sa largeur plus sa hauteur).

On vous garantit qu'il existe toujours au moins une flèche valide.

Exemple

entrée :

10
6 15
14 19
2 15
5 8
8 1
8 15
11 16
7 19
10 15
5 20

sortie :

25

Commentaires

L'exemple d'entrée représente le ciel étoilé illustré ci-dessus et la flèche la plus grande est indiquée sur le diagramme. Les trois étoiles formant cette flèche sont aux coordonnées (7,19), (8,1) et (14,19). Cette flèche a pour largeur 14-7=7 et pour hauteur 19-1=18, ce qui donne une taille totale de 7+18=25.

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 détaillée sera disponible lorsque vous aurez résolu le sujet.

Correction en cours de chargement…