← All solutions

Shortest judge solution: 1153 bytes. Shortest team solution (during contest): 977 bytes.

This was the “simple geometry problem” of the set. First notice that if all the wells are on one horizontal line, the well will hit only one of them, and it’s obviously best to hit the largest one. Otherwise, in a reasonably standard geometric reasoning, we can notice that its always possible to move the well so that it touches at least two of oil layer endpoints (first by shifting to, say, the left, and then by rotating).

So, a naive solution will be O(n³) — for each pair of points in the input that are not on a horizontal line, try drilling a well through these two points, and check which oil layers are hit by the well. This, however, will be too slow.

To speed it up, we will use a rotating sweep line. Pick any point P through which we will drill a well (we will iterate over all choices of P), and then sort all the other points not on the same horizontal line by the angle of the line through P and the other point. Then, we will rotate the well going through P by iterating over the other points, in slope order. If we encounter the first point of an oil layer, we add the value of this layer to the current result, if we encounter the second point, we subtract the value of this layer from the current result. This algorithm runs in O(n² log n) time, which is fast enough.

When implementing, one needs to take care when sorting by slope (that’s always tricky), and — as usually in sweep-line arguments — to deal correctly with tie-breaking (we need to first add layers, and then remove them). In particular, this means we need to store the slopes as pairs of integers, and not as floating points.