### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Sergey Kulik

**Editorialist:** Lalit Kundu

### DIFFICULTY:

CHALLENGE

### PROBLEM:

It is an interactive judge problem. You have a search area defined by n coordinate points that are present on the search area boundary. There is a point which you have to search for (that may or may not lie in the search area). You have m air-planes, which you can use. Each plane is defined by 3 variables (I, R, C). I is the unique id of the plane. R is the range it can transmit the special signal. C is the cost. You can use a plane to reach (x, y) which will cost 2*(x+y)*C, the judge will reply with “yes” or “no”, depending on if the search point is within the R manhattan distance of (x, y).

### EXPLANATION:

All the coordinates on the boundary are given in the input. And it is said that the whole search area can be enclosed in a 1024*1024 square. So we can actually shift the positions and always have x,y <1024. Now take the grid [1024][1024] and mark all boundary points. Now if you do a dfs from exterior point and stop on reaching marked points. you will end up marking all exterior points. So the unmarked points are interior points of search area. We can try all interior points, if we get the plane, we can report. if not we can report that it is out side.

To get better scores we can divide the 1024*1024 grid into smaller grids depending on available plane radius R, then query each of them, if we get an yes, then we can restrict our search to that area.

In contest, @mugurelionut and @aawisong, were able to pin point the exact positions by making assertions, hence they had the perfect score. All other scores are negligible considered to the perfect score, so every else had a score of 0.000.

This is what @aawisong had to say about this:

I was very interested in the problem ANUMFS.

I think this problem was so funny and combined with real circumstance.

In solving it, first of all I had tried to reduce the number of sending operation.

So, I sent the planes in the following way.

I find the planes which could investigate about half number of the points of search area.

Among those planes I choose the plane with the minimum operation cost and send it.

As the result, the number of points in search area to be investigated decreased half.

In this way, I could find the position of the missing flight by sending about log (number of points in search area) planes.

I sent planes with the probability theory more efficiently.

But one day, I noticed an interesting fact in the result of my submissions.

It was that the test data were static and the position of the missed flight was constant for each test case.

Because the problem was to find the position of the missed flight, this fact was very important.

I thought I could find the position of the missed flight without sending planes.

However, after several submissions, I could know the position of missing flight for each case.