Line Sweep Algo, Closest Pairs, and Red-Black Trees

[serur]

Hello fellows!

I've just got AC (1.047 CPU) 10245-"Closest Pair Problem" with algo explained in "Introduction".
My time is poor, however, than that of most of yours - and I suppose you used so-called "Line Sweep algorithm".
If you kindly give your comments on this account it will be greatly appreciated.
My problem here is that I need to implement such obscure thing as Red-Black tree (or AVL) before implementing sweep algo itself.
I must admit that all these "rotations" and "balancings" are quite difficult to understand, or at least not obvious, for my capacity (quite limited ).
Please, tell us of your own experience of mastering advanced search trees.

Thank you.

[Krzysztof Duleba]

std::set
http://www.sgi.com/tech/stl/set.html

[little joey]

I don't think 1 second is such a bad time for this problem. I don't think that the 'fast timers' use advanced algorithms. My algorith is simple:

Code: Select all

- read all the points;
- sort them by increasing x-coordinate;
- maxdist = infinity;
- for i = 1 to points-1:
   - for j = i+1 to points:
      - if x[j] - x[i] >= mindist break;
      - calculate dist(i,j);
      - if dist(i,j) < mindist update mindist;
- report mindist.

It should be noted that this algorithm only gives good times if the points are spread reasonably random through the xy-plane. It would collapse to O(n^2) if all the x-coordinates lie close to one value.

To improve the runtime of my program, I:
- replaced scanf("%lf") by my own reader based on getchar(), for a gain of 0.23 seconds;
- replaced the standard qsort() by a handwritten quicksort() for a gain of 0.18 seconds;
- cleaned up the inner loop by only using sqrt() when necessary for a gain of 0.02 seconds.

Overall my optimized program solves the problem in 0.180 seconds.

[serur]

Hi everyone!
And thank you for your replies.

I got a book by de Berg "Computational Geometry" (http://www.cs.uu.nl/geobook) and "Voronoi Diagrams", "Delanay Triangulation", "3D - Hulls" took my fancy.
Are there any problems in UVa that require the above things?
And I do believe that with your help this topic will become a good help for interested problem-hunters.

To Krzysztof Duleba:

The thing is, I'm not a C++ guy, but when I looked at C-code(of AVL trees, Red-Black Trees) from Richard Hethfield, Lawrewnce Kirby "The Art Of C Programming" I didn't feel encouraged in the slightest degree
Thank you, anyway, for I'd rather swtich to C++ soon I believe

[tywok]

I don't think there is one in this judge, but there is one at SPOJ : http://www.spoj.pl/problems/CH3D/

[serur]

Hello everyone!

Thank you for 3DHull!
Ars longa vita brevis est - so one shouldn't be content with geometrical stuff presented here in UVa...

As to the previous posts, I liked very much little joey's approach to the problem of poor time
little joey's observations about C - functions arise, in particular, this question: can one somehow contrive to optimize malloc() (free()) function?
For example, problem 540 - "Team Queue", good question on simulation and implementation technique. My code is got AC in 0.187 CPU, and I suspect malloc() and free() functions of having a good deal to do with slowing my code down.

Thank you.

PS. from symmetric considerations one can confer that putchar() is better than printf().

[little joey]

Well, let me issue a BIG warning here! Trying to outsmart standard functions and haxoring out the last clockcycle can be fun to do, but can also be very frustrating when you're not completely sure of what you are doing. Lots of hacks look promising at first sight, but turn out to be a complete waste of hours of coding when the resulting code is only slightly faster or even much slower than the original. Programming problems that require you to resort to such 'advanced techniques' to stay under the time limit, are bad programming problems. Period.

The message I wanted to communicate in my previous posting was: try to solve the problem using the simplest possible algorithm that is quick to implement, before you start off coding complex advanced algoritms that have better theoretical runtimes, but are much harder to implement correctly. Typing off a stupidly simple O(N^3) solution can often be done in 10 minutes, and has a good chance to solve the problem. And if not, well only 10 minutes are wasted, and you can always then decide to spend the rest of the contest time to implement this groovy O(N^1.534*ln ln N) algorithm....

[serur]

Yes, time is precious on contests

[nymo]

I follow your pseudocode and get ACC in 10245 and 10750 , Thanks for sharing your approach... it is quite simple and short , thanks again.

[Farsan]

What are some straight forward sweep line problems?