06 September 2005

Sweep line

I have known about sweep line for a long time but never implemented it. A week ago I was trying to solve TopCoder's FrogAndFly which clearly uses this technique. I have noticed that I'm very slow at implementing it. The experience was somehow similar to the one I had when I have implemented binary search for the first time: the idea seemed so simple to me that I never bothered to do it, yet when you do it for the first time you will be surprised how hard it is to get it right. It may even take more than 10 minutes!

Anyway, here is a program that hopefully illustrates the idea and presents an acceptable implementation for sweep line.

No comments:

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.