10553 - Treasure Map

[gvcormac]

Are you saying that I should take into consideration all points along the path and not only the endpoints of the segments?

You should be able to determine the answer from reading the question carefully.

Or you can a try it and see.

[BiK]

I found the treausure.

But one final question. I think that I should rotate with matrix:

(cos x, -sin x)
(sin x, cos x)

With this I rotate in positive direction - counterclockwise, which I think is the case of the problem. But the online-judge accepted my solution with matrix:

(cos x, sin x)
(-sin x, cos x)

[BiK]

Ok I figured it out. But I think that you should have used positive number in the problem statement when the magnetic north is to the west. After all that is the positive (counterclockwise) direction. Or this was intentionally changed in order to delude the competitors?

10x for keeping me in suspense the whole afternoon.

[gvcormac]

I found the treausure.

But one final question. I think that I should rotate with matrix:

(cos x, -sin x)
(sin x, cos x)

With this I rotate in positive direction - counterclockwise, which I think is the case of the problem. But the online-judge accepted my solution with matrix:

(cos x, sin x)
(-sin x, cos x)

Consider your example. The contest says that, for negative d, "magnetic north is west of true north." This means that the pirate treasure should be 90 degrees west of your final location. You have the opposite in your diagram. I'm not exactly sure which you're rotating (the pirate route or your route) so I have difficulty answering your question. But I'm pretty sure the judge's solution gets it right.

[Julien Cornebise]

What the program does is to find the points on my way to the treasure the first time I was on the island - findPoints().

[snip]

I get WA. I tried also looking for some careless mistake but I couldn't find any.

Perfect. Your description enables me to see you're oversight. I think Lain's example will help you to see it if you draw a picture.

Thank you, I was oversight too, and this example pointed my mistake. Thanks

[gvcormac]

Ok I figured it out. But I think that you should have used positive number in the problem statement when the magnetic north is to the west. After all that is the positive (counterclockwise) direction. Or this was intentionally changed in order to delude the competitors?

10x for keeping me in suspense the whole afternoon.

On a protractor, positive is counterclockwise. But in navigational coordinates, positive is clockwise. North is 0; East is 90; South is 180; East is 270.

I recall getting into a long confusing discussion with Skiena (until we clarified this point) when he was preparing "Radar Tracking" for inclusion in "Programming Challenges."

[Larry]

That's strange, I didn't know that, I just basically changed signs with what I did with the offset, got AC and assumed that I misread the problem somewhere...

Any advice for future problems?

(I am curious though, as the sample cases work for either way of the interpretation, if this was intentional or not.. )

[gvcormac]

That's strange, I didn't know that, I just basically changed signs with what I did with the offset, got AC and assumed that I misread the problem somewhere...

Any advice for future problems?

(I am curious though, as the sample cases work for either way of the interpretation, if this was intentional or not.. )

I'm not sure what you mean. +90 and -90 are distinguished by the sample cases.

It is pretty common in ACM problems to have incomplete sample cases. You have to use all the information in the problem to make sure you've got it right. In general, if you get WA, your first step should be to sit down and read every word of the problem statement very carefully. Then read every line of your program very carefully, and try to prove to yourself that your solution answers the question.

[Larry]

Hrmm, you're right, I apologize, I changed the test case a bit, and didn't realize I had it on the same file, where the +/- didn't matter...

I don't ask for a complete test case, just enough that you can't misintreprete the problem..

[drewsome]

I'm also having trouble with this problem. I got the solution for the sample input no problem, and also managed to calculate 1.29 for this testcase:
2
NE 2
S 1
-90

I'm pretty sure the problem is something to do with the way I handle angles.. I probably put too much faith in c++ trigonometric functions I would really appreciate it if someone would post some more extensive sample input/output, or if you want I can try to explain in detail how I am handling angles (although that would pain me, my geometry isn't as strong as it should be).

Thanks
- Andrew