Je me demande s'il ne serait pas possible de résoudre la partie 2 bien plus vite, en calculant l'aire des zones protégées par des rochers.
En effet, le nombre d'unités de sables tombées, c'est l'aire d'une triangle plein, moins celle des rochers qu'il contient, moins l'aire des zones protégées par ces derniers.
Ceci dit, déterminer la zone protégée par l'ensemble des rochers, c'est loin d'être évident. La zone protégée par un segment horizontal, c'est facile, c'est un triangle dessous. La zone protégée par un segment vertical, c'est facile, c'est rien du tout. Mais quand on commence à avoir des segments horizontaux et verticaux qui se touchent, ça devient compliqué.
Allez, une autre piste, sans doute pas beaucoup plus simple. On dirait qu'on peut déterminer la zone protégée par des rochers, non pas seulement par calcul, mais aussi par une simulation bizarre : faire couler de l'air depuis le bas vers le haut et regarder où il s'accumule. Mais ça pose le problème d'introduire cet air : il faut qu'il s'accumule et qu'il traverse en même temps les segments...
# Pistes pour la partie 2
Posté par 🚲 Tanguy Ortolo (site web personnel) . En réponse au message Avent du Code, jour 14. Évalué à 4.
Je me demande s'il ne serait pas possible de résoudre la partie 2 bien plus vite, en calculant l'aire des zones protégées par des rochers.
En effet, le nombre d'unités de sables tombées, c'est l'aire d'une triangle plein, moins celle des rochers qu'il contient, moins l'aire des zones protégées par ces derniers.
Ceci dit, déterminer la zone protégée par l'ensemble des rochers, c'est loin d'être évident. La zone protégée par un segment horizontal, c'est facile, c'est un triangle dessous. La zone protégée par un segment vertical, c'est facile, c'est rien du tout. Mais quand on commence à avoir des segments horizontaux et verticaux qui se touchent, ça devient compliqué.
Allez, une autre piste, sans doute pas beaucoup plus simple. On dirait qu'on peut déterminer la zone protégée par des rochers, non pas seulement par calcul, mais aussi par une simulation bizarre : faire couler de l'air depuis le bas vers le haut et regarder où il s'accumule. Mais ça pose le problème d'introduire cet air : il faut qu'il s'accumule et qu'il traverse en même temps les segments...