Manchots Glisseurs – Regional event 2019

Énoncé¶

Chaque année, Joseph assiste au célèbre concours de glisse qu'organisent les manchots sur la banquise pour profiter de l'été. Ce sport est très accessible car le seul matériel qu'il nécessite est une piste en ligne droite.

Cette année les manchots font face à un problème : la piste de glisse sur laquelle ils ont l'habitude de compétiter a fondu. Cependant, ils ne vont pas abandonner leur tradition pour autant et se mettent déjà la recherche d'un nouvel emplacement pour la compétition.

Pour des raisons symboliques, il faut que la nouvelle piste pointe vers le pôle, elle devra donc être alignée avec l'axe nord‑sud.

Afin de savoir si l'organisation du concours ne va pas être compromise, il va falloir trouver quelle est la plus grande piste de glisse qui va pouvoir être installée. Ils ont récolté une description des zones aménageables sur la banquise qui sont décrites par un ensemble de plaques de glaces rectangulaires disjointes.

Entrée¶

L'entrée comprendra :

Un entier sur la première ligne : la largeur $l$ de la zone où les manchots recherchent un emplacement.

Un entier sur la seconde ligne : la hauteur $h$ de la zone où les manchots recherchent un emplacement.

Un entier sur la troisième ligne : le nombre $n$ de plaques de glace qui sont présentes dans cette zone.

Sur les $n$ lignes suivantes seront indiqués 4 entiers pour décrire les plaques de glace :

• les deux coordonnées $x_i$ et $y_i$ du coin bas gauche de la plaque de glace ;
• les deux coordonnées $u_i$ et $v_i$ du coin haut droite de la plaque de glace.

L'axe nord‑sud correspond aux ordonnées : plus la deuxième coordonnée d'un point est grand, plus il est dirigé vers le nord.

Sortie¶

Affichez un entier : la longeur de piste la plus grande que l'on puisse envisager d'installer.

Contraites¶

• $1 \le l, h \le 10^6$
• $1 \le n \le 10^4$
• $0 \le x_i \le u_i < l$ et $1 \le y_i \le v_i < h$