Various methods of solving the closest pairs problem for UVA Online Judge.
The optimal minimal runtimes are as follows:
| Algorithm | Runtime (sec) |
|---|---|
| Heuristic (LR) | 0.069 |
| Divide & Conquer | 0.074 |
The first approach to solving the is a divide and conquer approach. This approach achieves a time complexity of O(nlog(n)) by using basic computational geometry to rule out many of the possibilities. This approach is implemented in this divide and conquer file.
Compiler: C++ 4.8.2 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE
The second approach to solving the closest pair problem is a left to right heuristic where we compute the distance between the two left most points and proceed right, recalculating is the x distance is less than the closest previous distance. This approach achieves a time complexity of O(n2). This approach is implemented in this heuristic file.
Compiler: ANSI C 4.8.2 - GNU C Compiler with options: -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE