Sans géométrie

Première partie

Pour la première partie, je fais du remplissage, voici les étapes :

1. J'alloue une matrice suffisante pour contenir tout le tracé – oui, il y a une étape pour déterminer la taille nécessaire, mais c'est sans intérêt à dérailler –, plus une marge d'une unité. En fait, pas une matrice mais trois, à valeurs booléennes : le terrain, une matrice qui indiquera si on est à l'extérieur du tracé, et une matrice qui indiquera si on a déjà visité chaque point.
2. Je trace les tranchées.
3. Je pars du point en haut à gauche, dont je suis certain qu'il est hors du bassin puisqu'il fait partie de la marge sus-mentionnée. De proche en proche, je remplis l'extérieur du bassin dans la seconde de mes matrices. C'est beaucoup plus facile que d'essayer de remplir directement l'intérieur. La troisième matrice sert à cette étape, pour ne pas passer indéfiniment sur les mêmes points.
4. Je remplis l'intérieur du bassin dans la matrice du terrain, la seule que je vais garder.

Trouver l'aire, c'est trivial.

Deuxième partie

Pareil. Comment ça, pareil, alors que les coordonnées sont beaucoup trop grandes pour pouvoir faire ça avec des matrices ? Eh bien, on n'a pas besoin de toutes les coordonnées, voyez-vous. On a seulement besoin de celles où commencent ou finissent des tranchées en fait.

Bref, je me construis une matrice donc les cases ont des dimensions virtuelles carrément variables. Ensuite, on se ramène à l'algorithme précédent, avec un détail de pondération pour le calcul de l'aire.