La force contre la flotte – Qualification 2020

Niveau 5

Énoncé

Joseph Marchand, dernier Jedi de Prologin, se prépare pour la plus grande bataille qu'il ait jamais mené, il a un plan mais a besoin de votre aide.

Il va affronter aux côtés des rebelles une flotte de vaisseaux de l'empire. Sa stratégie est d'immobiliser les vaisseaux pour que les rebelles puissent aller attaquer leurs points faibles.

La flotte est répartie sur un plan 2D. Pour immobiliser un vaisseau il faut couvrir toute sa surface de ligne de force. Joseph Marchand n'est pas certain de pouvoir contenir tous les vaisseaux, il vous demande donc à vous, ingénieur·e algorithmique de la rébellion, de calculer le nombre minimal de lignes de force à déployer pour recouvrir toute la flotte.

Les lignes de force peuvent être uniquement verticales ou horizontales, mais jamais en diagnonales. On peut profiter que deux vaisseaux soient côte à côte pour les couvrir par une même ligne de force mais si du vide les séparent c'est impossible, il faudra deux lignes de force distinctes.

La flotte se présente sous la forme d'une carte à deux dimensions de largeur $l$ et de hauteur $h$, où les $N$ vaisseaux sont rectangulaires et représentés par deux points, un en haut à gauche et l'autre en bas à droite. À noter que les vaisseaux peuvent se superposer, et on notera $S$ la surface prise par l'ensemble des vaisseaux de la flotte.

Entrée

L'entrée contiendra :

  • Sur la première ligne, un entier : $l$, la largeur de la carte.
  • Sur la ligne suivante, un entier : $h$, la hauteur de la carte.
  • Sur la ligne suivante, un entier : $N$, le nombre de vaisseaux dans la flotte.
  • Sur les lignes suivantes, une liste de $N$ éléments : flotte, une liste de vaisseaux.
    • Une ligne par élément de la liste : séparés par des espaces, un entier $x$ (abscisse du coin haut-gauche), un entier $y$ (ordonnée du coin haut-gauche), un entier $u$ (abscisse du coin bas-droit), et un entier $v$ (ordonnée du coin bas-droit).

Sortie

Afficher le nombre minimal de lignes de force à déployer pour couvrir toute la flotte.

Contraintes

  • $1 ≤ l ≤ 1000000$
  • $1 ≤ h ≤ 1000000$
  • $1 ≤ N ≤ 10000$
  • $1 ≤ S ≤ 10000$
  • $0 ≤ x ≤ l$
  • $0 ≤ y ≤ h$
  • $x < u ≤ l$
  • $y < v ≤ h$

Contraintes d'exécution

Utilisation mémoire maximum
5000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
5
3
3 2 4 3
1 3 5 4
3 4 4 5
Exemple de sortie
2
Commentaire

Les 3 vaisseaux peuvent être couverts par 2 lignes de force.

Exemple d'entrée
5
5
2
0 2 2 4
3 2 4 3
Exemple de sortie
3
Commentaire

Les 2 vaisseaux peuvent être couverts par 3 lignes de force, deux ne suffisent pas à cause du vide entre les vaisseaux.