-
One horizontal rod and one vertical rod is placed on a
(hidden) N x N grid.
-
The only way to find out information about the rods is
to call a library function rect(x1,y1,x2,y2), x1 < x2,
y1 < y2.
This function returns 1 if any part of either rod lies within the
rectangle defined by top left corner (x1,y1) and (x2,y2), 0 otherwise.
-
Make as few calls as possible to the library function.
Your score depends on the number of calls you make to
rect(...).
For example, in the picture below the call to
rect(x1,y1,x2,y2) returns 1.
(x1,y1)
. . . . ___________ . . .
. . . . | . . . . | . . .
. . . x | . . . . | . . .
. x x x x x x x x | . . .
. . . x | . . . . | . . .
. . . x |_________| . . .
. . . x . . . . . (x2,y2)
. . . x . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
Solution
-
Starting with the full rectangle, use binary search
to narrow down to a single "x".
-
Probe the four directions around this "x" to check
whether it is a vertical or horizontal rod (or a
crossing point of two rods).
-
Having got the orientation, do a binary search along
that line (use rectangles in which one dimenstion is 1)
to find the end points.
-
Assume that the rod we have found is the horizontal
one. Query the rectangles (strictly) above and below
the rod to find an "x" from the vertical rod.
-
Again, use binary search to narrow it down to a single
"x" and then use binary searches along the vertical line
containing this "x" to find the end points.