À un certain instant, appelé instant initial, les cyclistes participant à une course sur route se trouvent à des distances de $x_1,x_2,\ldots,x_n$ mètres du départ ($n$ est le nombre total de cyclistes). Chaque cycliste se déplace à sa propre vitesse constante ; les vitesses sont $v_1,v_2,\ldots,v_n$ mètres par seconde. Tous se déplacent dans le même sens.

Un journaliste couvrant la compétition veut déterminer l’instant où la distance entre le cycliste en tête et le dernier est minimale, afin de photographier tous les participants à la course en même temps depuis un hélicoptère.

Écrivez un programme qui, connaissant le nombre de cyclistes $n$, leurs positions initiales $x_1,x_2,\ldots,x_n$ et leurs vitesses $v_1,v_2,\ldots,v_n$, calcule un instant $t$ où la distance $l$ entre le premier et le dernier cycliste est minimale.

Entrée

La première ligne du fichier d’entrée contient un entier $n$, le nombre de cyclistes.

Les $n$ lignes suivantes contiennent chacune deux entiers : $x_i$, la distance du départ au cycliste $i$ à l’instant initial ($0\le x_i\le10^7$), et $v_i$, sa vitesse ($0\le v_i\le10^7$).

Sortie

Écrivez deux nombres réels dans le fichier de sortie : $t$, le temps en secondes écoulé depuis l’instant initial jusqu’à ce que la distance en mètres entre le premier et le dernier soit minimale, et $l$, cette distance.

Les nombres $t$ et $l$ doivent avoir une erreur absolue ou relative ne dépassant pas $10^{-6}$. Cela signifie que, si le nombre affiché vaut $x$ et la réponse correcte vaut $y$, la réponse est correcte si $|x-y|/\max\{1,|y|\}$ ne dépasse pas $10^{-6}$.

Exemples

Entrée 1

3
0 40
30 10
40 30

Sortie 1

1 30

Entrée 2

5
90 100
100 70
100 70
110 60
120 35

Sortie 2

0.5 5.000000000000

Sous-tâches

Ce problème comporte quatre sous-tâches. Chaque sous-tâche est évaluée avec son propre groupe de tests. Les points d’une sous-tâche sont attribués uniquement si tous les tests de ce groupe sont réussis.

Sous-tâche 1 (20 points)

$2\le n\le50$, $0\le x_i\le1000$, $0\le v_i\le1000$. Il est garanti qu’il existe une réponse dans laquelle $t$ est un entier ne dépassant pas $1000$.

Sous-tâche 2 (20 points)

$2\le n\le200$.

Sous-tâche 3 (30 points)

$2\le n\le2000$.

Sous-tâche 4 (30 points)

$2\le n\le10^5$.

Retour d’évaluation

Pendant l’épreuve, vous pouvez demander au plus 10 fois les résultats de votre programme sur les tests du jury. Les demandes ne peuvent être faites plus souvent qu’une fois toutes les 5 minutes. Pour chaque test, le résultat de l’exécution du programme sur ce test est communiqué.

Dans ce problème, vous pouvez choisir la solution qui sera évaluée. Dans ce cas, les points sont attribués à la meilleure des solutions suivantes :

• la solution explicitement choisie ;
• la dernière solution acceptée pour évaluation.

Si aucun choix n’est fait, la meilleure des solutions suivantes sera évaluée :

• les solutions dont les scores ont été consultés ;
• la dernière solution acceptée pour évaluation.