Prologin
2025
Énoncé¶
Haruhi veut observer les troupes de lions présentes dans la savane et trouver celle dont le territoire est le plus étendu. Pour cela elle répertorie les positions de tous les lions présents dans sa zone de recherche.
Une troupe de lion est constituée d'un seul mâle dominant et de femelles partant à la chasse.
Haruhi considère que la position d'une troupe correspond à celle du mâle dominant, et qu'une femelle appartient à la troupe dont elle est la plus proche en distance de Manhattan.
La taille du territoire d'une troupe correspond à la somme des distances entre chaque femelle d'une troupe et le mâle.
On considère qu'une lionne ne peut être à la même distance de deux lions.
Distance de Manhattan¶
La distance de Manhattan est la distance entre deux points d'un quadrillage représentant la distance parcourue afin de rejoindre ces deux points en suivant les lignes du quadrillage. Par exemple deux points A(1, 4) et B(4, 1) auront une distance de Manhattan de 6.
Entrée¶
Une position est représentée par les coordonnées en abscisse et ordonnée x y
sur une seule ligne séparées par un espace.
L’entrée contiendra :
- Sur la première ligne, un entier : m, taille de la liste des mâles.
- Sur la ligne suivante, un entier : f, taille de la liste des femelles.
- Sur les lignes suivantes, une liste de m éléments : males, liste des positions des mâles.
- Sur les lignes suivantes, une liste de f éléments : femelles, liste des positions des femelles.
Sortie¶
Afficher sur la sortie standard la taille de la plus grande troupe présente.
Contraintes¶
- $0 < m ≤ 10000$
- $0 < f ≤ 10000$
- $0 ≤ x ≤ 10000$
- $0 ≤ y ≤ 10000$
