Prologin
2025
Énoncé¶
Joseph Marchand décide d'aller faire un tour près de la très célèbre cascade d'eau de la région. Elle tient sa célébrité de sa particularité d'écoulement : à chaque emplacement infinitésimal où l'eau peut s'écouler au sein de la cascade, le débit d'écoulement ne peut pas dépasser une quantité $\delta$ de molécules d'eau par seconde. Il y a de multiples rochers culminants dans la cascade, et l'eau ne peut bien sûr pas passer au travers. Une fois arrivé à la cascade, Joseph se demande alors quel débit d'eau maximal peut-être obtenu à travers la cascade.
Aidez Joseph en écrivant un algorithme qui calcule ce débit maximal. Vous arrondirez ce débit à l'entier inférieur le plus proche.
La cascade est considérée comme étant une surface verticale de hauteur $H$ et de largeur $L$. Le débit $\delta$ est donc exprimé en $L\cdot s^{-1}\cdot m^{-1}$. Vous devez trouver le débit maximal à travers la cascade en $L\cdot s^{-1}$.
Les rochers sont considérés comme étant des polygones (pas nécessairement convexes) sur cette surface.
Entrée¶
L'entrée contiendra plusieurs lignes.
Sur la première ligne il y aura deux entiers $H$ et $L$, la hauteur et la largeur de la cascade.
Sur la seconde ligne il y aura un entier $N$, le nombre de rochers. Vous trouverez ensuite $N$ fois :
- une ligne avec un entier $M_i$, le nombre de points du i-ème polygone.
- $M_i$ lignes contenant 2 entiers $x_{ij}$ et $y_{ij}$ l'abscisse (dans le sens de la largeur) et l'ordonnée (dans le sens de la hauteur) du j-ème point du i-ème polygone.
Enfin, la dernière ligne contiendra un entier $\delta$, le débit d'eau par mètre maximal de la cascade.
Sortie¶
Vous afficherez un entier, le plus grand débit qu'il est possible de faire passer au travers de la cascade.
Contraintes¶
- $1 \le H \le 1\ 000$
- $1 \le L \le 1\ 000$
- $0 \le N \le 100$
- $3 \le M_i \le 10$
- $0 \le x_{ij} \le L$
- $0 \le y_{ij} \le H$
- $1 \le \delta \le 100$
