Cascade – Épreuve régionale 2017

Niveau 8

É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$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
7 5
2
4
0 1
1 1
1 5
0 5
4
4 1
5 1
5 5
4 5
14
Exemple de sortie
42
Commentaire

00.png

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

01.png