Prologin
2024
Énoncé¶
Joseph Marchand a décidé de se lancer dans une nouvelle aventure, qu'il espère la plus lucrative possible : le taxi-motoneige, avec sa SUPERBE motoneige Nimbus 4242 ™.
Pour ce faire, il reçoit un certain nombre de requêtes de clients, qu'il doit aller chercher à leur position actuelle, puis emmener à destination. Heureusement pour lui, les clients savent la chance qu'ils ont de pouvoir admirer une motoneige Nimbus 4242 ™, et n'en voudront en conséquence pas à Joseph s'il prend son temps pour les chercher ou s'il les transporte à leur destination de manière particulièrement inefficace. Si, durant une course, Joseph Marchand veut s'arrêter pour observer sa motoneige Nimbus 4242 ™, il le peut: quel veinard !
Il peut aussi, quand il le désire, s'arrêter dans différentes stations-services situées sur la carte pour se recharger en carburant. Comme les pompistes admirent sa motoneige Nimbus 4242 ™, le carburant est gratuit pour notre chauffeur de taxi.
Intéressons-nous maintenant à sa motoneige Nimbus 4242 ™. Il s'agit d'une motoneige quatre places : c'est à dire qu'elle peut accueillir Joseph et au plus trois clients. De plus, elle fonctionne beaucoup moins bien quand elle a moins de carburant : plus exactement, s'il parcourt une certaine distance en kilomètres entre deux passages dans des stations-service, il aura consommé un litrage de carburant égal au carré de cette distance (calculée, évidemment, à vol d'oiseau, car la motoneige Nimbus 4242 ™ ne s'embarasse pas des obstacles).
Devant changer son réservoir, Joseph aimerait bien savoir quel est le volume minimal, en litres, qu'il doit supporter pour pouvoir répondre à toutes les requêtes, sachant qu'il commence dans la première station décrite, qu'il doit rentrer dans icelle après avoir satisfait toutes les requêtes et qu'il n'existe que des réservoirs avec des contenances entières.
Entrées¶
L’entrée comprendra :
- un entier naturel N représentant le nombre de stations-service ;
- un entier naturel M représentant le nombre de requêtes ;
- sur chacune des N lignes suivantes, deux entiers $x_i$ et $y_i$ correspondants aux coordonnées de la i-ème station : Joseph Marchand part de la première de ces N stations ;
- sur les M lignes suivantes, quatres entiers $a_j$, $b_j$, $c_j$ et $d_j$ séparés par des espaces : $(a_j , b_j )$ représente le point de départ de la j-ème requête alors que $(c_j , d_j )$ représente la destination de cette j-ème requête.
Sortie¶
Vous afficherez en sortie :
- Un entier : la contenance minimale (en litres) du réservoir de Joseph Marchand.
Contraintes¶
- $1 \le N \le 10\ 000$
- $1 \le M \le 10$
- $-100\ 000 \le x_i \le 100\ 000$
- $-100\ 000 \le y_i \le 100\ 000$
- $-100\ 000 \le a_i \le 100\ 000$
- $-100\ 000 \le b_i \le 100\ 000$
- $-100\ 000 \le c_i \le 100\ 000$
- $-100\ 000 \le d_i \le 100\ 000$