Prologin, the French National Computer Science Contest

Énoncé¶

En l'an 2101, après une guerre nucléaire massive entre les utilisateurs de Vim et d'Emacs, la surface de la terre est entièrement ravagée. Menacée par un hiver nucléaire impitoyable, l'humanité s'est réfugiée depuis plusieurs années dans un gigantesque système de grottes souterraines, reliées entre elles par de petites galeries.

Ayant peine à recréer un semblant de civilisation, les survivants cherchent à moderniser l'infrastructure souterraine en construisant un métro qui pourrait relier toutes les galeries souterraines entre elles. Mais la vie est parfois dure dans une société dystopique post-apocalyptique, et les ingénieurs en charge des travaux n'ont de ressources que pour une ligne de métro, qui ne pourra aller qu'en ligne droite.

Étant donné l'abscisse et la profondeur de chaque grotte, comment construire le métro pour minimiser le carré des distances minimales de galeries à creuser pour relier chaque grotte au métro ?

Entrée¶

Sur la première ligne, le nombre de grottes $N$.
Sur les $N$ lignes suivantes, des couples d'entier $(x, y)$ correspondant à l'abscisse et à la profondeur de chaque grotte.

Sortie¶

Un entier représentant le minimum de la somme des carrés des distances de galeries à creuser pour que chaque grotte soit reliée au métro, arrondi à l'entier inférieur.

Contraintes¶

$1 ≤ N ≤ 1000$
$1 ≤ x ≤ 100000$
$1 ≤ y ≤ 100000$

Runtime constraints

Maximum memory usage: 1000 kilobytes
Maximum execution time: 1000 milliseconds

Input/output samples

Sample input

Sample output

Note

Dans cette configuration, on a :

une grotte A d'abscisse 10 et de profondeur 10 ;
une grotte B d'abscisse 30 et de profondeur 60 ;
une grotte C d'abscisse 75 et de profondeur 75 ;

La meilleure façon de placer le métro est en positionnant le métro en suivant la droite $y = 1.026x + 9.013$.

Le carré de la distance avec la première grotte est de ~41.9, celui de la deuxième est de ~199.1 et celui la troisième ~58.39. En arrondissant à l'entier inférieur, la somme totale des carrés des distances des grottes avec le métro est de 299.