Find coordinates of a rectangle by asking <= 7 queries
We are given a hidden rectangle. We can ask the computer a maximum of 7 queries and in each query, we specify a coordinate x,y. The computer then returns the minimum manhattan distance between this point and any point on the sides of this rectangle i.e the point(x0,y0) which lies closest to our query point and lies on one of the sides of this rectangle. We have to find the coordinates of the lower left and upper right vertices of the rectangle.
The points are strictly positive and lie in the range of 0 to 1000000000
Till now, I have generated 4 equations involving the 4 vertices of the rectangle but the problem is that there are infinite solutions for my system of linear equations generated.
Please help.
Last edited on
Hello honeybuzz,
You wrote:
So where is your code?
No none can help you fix or correct what they can not see. And you may be waiting a long time if you think someone will write the program for you.
Even if it is wrong or not working post what code you have and all the variations of the equation that you have tried.
In may case the math, (manhattan distance), is beyond what I know, but I can usually make a program work with a little research.
Give those that read your question something to work with.
Andy
You wrote:
| Till now, I have generated 4 equations involving the 4 vertices of the rectangle but the problem is that there are infinite solutions for my system of linear equations generated. |
So where is your code?
No none can help you fix or correct what they can not see. And you may be waiting a long time if you think someone will write the program for you.
Even if it is wrong or not working post what code you have and all the variations of the equation that you have tried.
In may case the math, (manhattan distance), is beyond what I know, but I can usually make a program work with a little research.
Give those that read your question something to work with.
Andy
you have to understand the math to solve this in code.
can you solve this by hand, without any code?
can you solve this by hand, without any code?
> a maximum of 7 queries
> the minimum manhattan distance between this point and any point on the sides of this rectangle
> The points are strictly positive and lie in the range of 0 to 1000000000
unless I misunderstood this can be done with just 4 queries
(0, 0) gives me the distance to the bottom left vertex
(0, 1000...) to the bottom right vertex
the next querie (which is left as an exercise to the reader) gives the y of the bottom side (y_B). With that you compute x_L and x_R
and with a symetric query you may obtain y_T
¿the rectangle is axis aligned?
> the minimum manhattan distance between this point and any point on the sides of this rectangle
> The points are strictly positive and lie in the range of 0 to 1000000000
unless I misunderstood this can be done with just 4 queries
(0, 0) gives me the distance to the bottom left vertex
(0, 1000...) to the bottom right vertex
the next querie (which is left as an exercise to the reader) gives the y of the bottom side (y_B). With that you compute x_L and x_R
and with a symetric query you may obtain y_T
¿the rectangle is axis aligned?
Last edited on
Topic archived. No new replies allowed.