Roches martiennes

Le module dont vous vous occupez est chargé de la sélection des échantillons les plus susceptibles de contenir certains métaux lourds. Plusieurs séries d'analyses sont prévues pour sélectionner un certain nombre d'échantillons, et votre module est chargé du choix final des deux échantillons les plus prometteurs, qui sont ceux les plus denses.

Ecrivez un programme qui prend en entrée une liste de descriptions d'échantillons, avec pour chacun son volume et son poids, et qui choisit et affiche les numéros des deux échantillons les plus denses, c'est-à-dire, dont le rapport poids/volume est le plus grand.

• 2 <= N <= 300 000, où N est le nombre d'échantillons.
• 1 <= V <= 100 000, où V est le volume d'un échantillon.
• 1 <= P <= 100 000, où P est le poids d'un échantillon.

On vous garantit qu'il n'y aura pas deux échantillons de même densité. On vous garantit également que la différence entre deux densités d'échantillons est toujours supérieure à 10^-6.

La première ligne de l'entrée contient un entier N : le nombre d'échantillons.

Les N lignes suivantes décrivent les échantillons, du numéro 1 jusqu'au numéro N (inclus). Chacune de ces lignes contient deux entiers séparés par un espace : P et V, respectivement le poids et le volume de l'échantillon décrit.

Vous devez écrire sur la sortie les identifiants des deux échantillons les plus denses, en commençant par le plus dense. Ecrivez le tout sur une seule ligne, en séparant les deux entiers que vous affichez par un espace.

Rappel : les identifiants sont des entiers compris entre 1 et N inclus.

Les densités (ici arrondies à 10^-6) des échantillons de l'exemple proposé sont :

1,677419
0,995272
2,000000
0,050613
2,900000

Entrées-Sorties en C++

Pour inclure la bonne bibliotèque :
   
   #include <stdio.h>

Pour lire le nombre d'échantillons :

   int nombre;
   scanf("%d", &nombre);

Pour lire chaque échantillon :

   int poids, volume;
   scanf("%d%d", &poids, &volume);

Pour afficher le résultat :

   printf("%d %d\n", meilleurIndex1, meilleurIndex2);

Entrées-Sorties en Caml

Pour lire le nombre d'échantillons :

   let nombre = Scanf.scanf " %d" (fun x -> x) in

Pour lire chaque échantillon :

   let poids, volume = Scanf.scanf " %d %d" (fun x y -> x,y) in

Pour afficher le résultat :

   Printf.printf "%d %d\n" meilleurIndex1 meilleurIndex2;