Belle étoile

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.


Source : http://www.france-ioi.org/ Créé par : FARIO 2004 [Mathias Hiron].