Ri, the Miner
We can notice that the query points lie on the same line, either parallel to x axis or parallel to y axis. We call this the query line. We can assume that the line is parallel to x axis. If not we can just swap (x,y) to make it parallel to x axis. Thus we now don’t need to worry about the y coordinate.
Now we instead of 2D coordinate we just think along the query line. And each mine will be represented as the intersection of the circle and the query line.
See the image above to better understand the sample test. The yellow cross indicates the intersection of circle 1 with query line, the blue cross for circle 2 and the green cross for circle 3. And the red crosses indicates the queries. We can immediately see that if a query point if is inside a circle then it will also be within the intersection of the circle with the query line. We store the start and end of the intersection of the circle with relevant information like its index, gold amount etc and the queries too.
Thus the problem reduces to a sweep line problem. We sort the points at first based on their coordinate (Remember we are now only working with x coordinate). If the coordinate is same we prioritize start intersection points, then the query points then finally the end intersection points. We sweep from left to right on the points. We do the following things in order.
If the point is a start, we insert that mine information in a set.
If the point is a query, then we find the mine with most amount of gold from the set.
If the point is a end, we remove that mine from the set.
Things to note here is that, the queries will be out of order. So we need to rearrange them and answer in the correct order. Also we need to check if the query is not inside any active mine.
Now, to find the intersection points we can use simple high school geometry. The radius is given and the height is the distance of the center from the query line. We calculate half of the chord length rounded down to the nearest integer. Then we subtract that from the center to find left or start intersection and add the length to get right or end intersection.
The complexity of the solution is
