Re: jour 9

Pour ma part, j'ai essayé de ne pas utiliser de librairies externes même si c'est très pratique.
La partie 1 est facile.
J'ai mis beaucoup de temps à débugguer la partie 2 à cause de bugs stupides.

Voici l'idée pour la partie 2.
Bien sûr, on ne peut pas représenter la grille des points de l'input car elle est beaucoup trop grande.
Ce qu'on va faire, c'est qu'on va utiliser une grille plus petite.
On trie les coordonnées x et y par ordre croissant et dans la grille au lieu d'utiliser la position (x, y), on va utiliser la position (i, j) où i est la position de x dans son tableau trié et j est la position de y dans son tableau trié.
Ce qui nous permet d'avoir une grille de taille environ 250x250, ce qui est raisonnable.
Ensuite, on trace des lignes dans la grille en fonction des segments données en input et on remplit le polygone en utilisant le classique flood-filling.

Maintenant, il y a une astuce pour déterminer en temps constant si un rectangle est contenu dans le polygone.
L'idée est de calculer, par programmation dynamique, un tableau empty_table qui pour chaque (x, y) donne combien de cases vides contient le rectangle (0, 0) -- (x, y).
A partir de là, on peut déterminer déterminer le nombre de cellules vides dans un rectangle (x1, y1, x2, y2) en faisant le calcul
empty_table[x2, y2] - empty_table[x1-1, y2] - empty_table[x2, y1-1] + empty_table[x1-1, y1-1].
Si le nombre de cellules vides est 0, cela signifie que le rectangle est contenu dans le polygone.

Ca donne un algorithme en temps O(n2) et un temps d'exécution de 650 microsecondes pour les deux parties.
Je ne fais pas de supposition sur l'input, on peut sans doute faire mieux en en faisant.