The intended solution passes all vertical lines in increasing order of their x values and keeps a list of active y intervals. At each "stop", i.e. for every vertical line, it does the following:

• multiply the x distance to the previous stop with the size of the interval that is the union of all active y intervals,
• add the result of this multiplication to the total result,
• update the set of active y intervals.

The scan line is implemented as a full binary tree over range ~0 \dots 3 \times 10^4~ (whole structure is hidden in array, like in standard heap implementation). Every node of the tree consists:

• number of edges which cover whole interval
• summary length of covered space in the interval defined by subtree of vertex

The complexity of this solution is ~\mathcal O(n \log c)~, where ~c~ is the maximum y coordinate.