Op de oceaanbodem bots je op een veld met hydrothermale bronnen¹! Deze bronnen produceren constant grote, ondoorzichtige wolken. Het is dus best om ze zoveel mogelijk te vermijden.

Ze hebben de neiging om lijnen te vormen. De onderzeeër produceert een handige lijst van alle lijnen met bronnen (de invoer voor deze opgave) die je kunt bekijken. Bijvoorbeeld:

0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2

Elke lijn met bronnen wordt gegeven als een lijnsegment in het formaat x1,y1 -> x2,y2 waarbij x1,y1 de coördinaten zijn van het ene uiteinde van het lijnsegment en x2,y2 de coördinaten van het andere uiteinde. De punten aan beide uiteinden maken zelf ook deel uit van het lijnsegment. Met andere woorden:

• Een lijnsegment 1,1 -> 1,3 bedekt de punten 1,1, 1,2, en 1,3.
• Een lijnsegment 9,7 -> 7,7 bedekt de punten 9,7, 8,7, and 7,7.

Voorlopig houden we enkel rekening met horizontale en verticale lijnen: lijnen waarvoor ofwel x1 = x2 of y1 = y2.

De horizontale en verticale lijnen uit de voorgaande lijst leveren dus het volgende diagram op:

.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....

In dit diagram zijn de coördinaten van de linkerbovenhoek 0,0 en die van de rechterbenedenhoek 9,9. Elke positie wordt weergegeven als het aantal lijnen dat het punt bedekt of als een . als er geen enkele lijn is die het punt bedekt. Het paar 1-en linksboven komt bijvoorbeeld van het lijnsegment 2,2 -> 2,1. De onderste rij wordt dan weer gevormd door de overlappende lijnen 0,9 -> 5,9 en 0,9 -> 2,9.

Om de gevaarlijkste gebieden te vermijden, moet je bepalen hoeveel punten er door minstens twee lijnen bedekt worden. In het bovenstaande voorbeeld is dat het geval voor alle punten waar in het diagram een 2 of groter staat - dat zijn in totaal 5 punten.

Opgave

Beschouw enkel de horizontale en verticale lijnen. Hoeveel punten worden door minstens twee lijnen bedekt? Bepaal dit op de volgende manier:

• Schrijf een functie overlap waaraan de padnaam (String) moet doorgegeven worden van een tekstbestand met een lijst van de nabijgelegen lijnen met bronnen. De functie moet teruggeven hoeveel punten (Int) door minstens twee lijnen bedekt worden, als we enkel rekening houden met horizontale en verticale lijnen.

Voorbeeld

In deze interactieve sessie gaan we ervan uit dat de tekstbestanden lines01.txt² en lines02.txt³ zich in de huidige directory bevinden.

> overlap ("lines01.txt")
5 :: Int
> overlap ("lines02.txt")
7674 :: Int