.The way I am thinking about doing this problem is as follows:
Read a ghost's posistion, check and see if this ghost is independent from all other ghosts. I define independent as that its angle between its two points from the shooter does not contain any endpoints of other ghosts and vice-versa no other ghost contains the endpoints of this ghost.
If it is independent you add it to the list and continue reading ghosts. If it is not independent then you check and see if this ghost is contained fully by one ghost. If so continue reading as this ghost is essentially useless information. Otherwise, check the other extreme and see if this ghost fully contains one or multiple ghosts and remove them for the same reason. If any ghosts were removed recheck if it is independent.
If it is still not independent then the last case is the tricky one. Since we have determined this ghost is not independent it means one point of this ghost is contained by another ghost or both points are contained by two different ghosts.
There are two ways I can think of to deal with this case. The hard way would be to determine the point of intersection on the ghost where the shot would be and then make the contained point to that new value. However this means that the new point will most likely not be an integer point and complicate further computations.
My other thought would be to just set the contained point to the containing ghosts endpoint so that it no longer contains that point and now you have the added usefulness that the new point is an integer point and that its new angle will be the exact same as if you were to calculate the intersection and change to that point. The only other thing you would need to worry about is when this ghost has both its endpoints contained by two different ghosts if the end result is that the new endpoints are the same value then really this ghost was completely covered by those two ghosts and you can disregard this ghost and continue reading.
Now that you have all that tricky stuff dealt with
you can go ahead and try and calculate the minimum angle to kill all remaining ghosts with the specified amount of shots. This is also a little tricky and I havent come up with a definte solution.For example taking the sample input with an added point to better explain the last case:
Code: Select all
1
5 3 0 0
2 2 2 -2 (ghost 1)
3 3 3 1 (ghost 2)
4 2 8 2 (ghost 3)
-6 1 -6 0 (ghost 4)
4 -1 1 -4 (ghost 5)
After going through the steps I have explained ghost 2 and 3 can be removed since they are fully contained by ghost 1. Also since ghost 5 has one point contained by ghost 1 we move ghost's 5 endpoint to ghost 1's endpoint as shown:
(note: ghost 1's endpoint could also have been changed to ghost 5's endpoint and given the same effect.)
Now you have 3 remaining ghosts and you can calculate the solution, which for this I got to be 60.4818.
So after hearing all of my thoughts, you guys spot any problems with my thinking or have any thing else to add to help solve this difficult problem?
