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

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

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

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 ).

Thank you.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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
Last edited by serur on Tue Aug 26, 2008 10:18 am, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am
I don't think there is one in this judge, but there is one at SPOJ : http://www.spoj.pl/problems/CH3D/
Impossible is nothing

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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().
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Yes, time is precious on contests
Last edited by serur on Tue Aug 26, 2008 10:19 am, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

THANKS LITTLE JOEY ...

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
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

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

What are some straight forward sweep line problems?