Hiver Nucléaire – Regional event 2020

Level 8

É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
3
10 10
30 60
75 75
Sample output
299
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.

Sample input
4
20 40
12 85
80 55
80 12
Sample output
1308
Note

Submit your solution

You have to register or log in to be able to submit your solution.