amh1k/daa-algorithm-visualizer

1// Q2 Part (i): Closest Pair of Points - Divide & Conquer O(n log n)2#include <iostream>3#include <fstream>4#include <vector>5#include <cmath>6#include <algorithm>7#include <limits>8#include <chrono>9#include <sstream>10#include <iomanip>11using namespace std;12 13struct Point {14    double x, y;15};16 17double dist(const Point& p1, const Point& p2) {18    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));19}20 21struct Result {22    Point p1, p2;23    double d;24    Result() : d(numeric_limits<double>::max()) {}25};26 27// Trace structure for visualization28struct TraceStep {29    string type; // "divide", "base_case", "left_recurse", "right_recurse", "strip_check", "merge"30    int depth;31    double divideX;32    vector<Point> points;33    Result currentBest;34    vector<Point> stripPoints;35    double stripWidth;36 37    string toJSON() const {38        stringstream ss;39        ss << fixed << setprecision(2);40        ss << "{";41        ss << "\"type\":\"" << type << "\",";42        ss << "\"depth\":" << depth << ",";43        ss << "\"divideX\":" << divideX << ",";44        ss << "\"points\":[";45        for (size_t i = 0; i < points.size(); i++) {46            ss << "{\"x\":" << points[i].x << ",\"y\":" << points[i].y << "}";47            if (i < points.size() - 1) ss << ",";48        }49        ss << "],";50        ss << "\"currentBest\":{";51        ss << "\"p1\":{\"x\":" << currentBest.p1.x << ",\"y\":" << currentBest.p1.y << "},";52        ss << "\"p2\":{\"x\":" << currentBest.p2.x << ",\"y\":" << currentBest.p2.y << "},";53        ss << "\"distance\":" << currentBest.d;54        ss << "},";55        ss << "\"stripPoints\":[";56        for (size_t i = 0; i < stripPoints.size(); i++) {57            ss << "{\"x\":" << stripPoints[i].x << ",\"y\":" << stripPoints[i].y << "}";58            if (i < stripPoints.size() - 1) ss << ",";59        }60        ss << "],";61        ss << "\"stripWidth\":" << stripWidth;62        ss << "}";63        return ss.str();64    }65};66 67vector<TraceStep> trace;68 69Result bruteForce(vector<Point>& pts, int l, int r, int depth, bool enableTrace) {70    Result res;71    for (int i = l; i < r; i++)72        for (int j = i+1; j <= r; j++) {73            double d = dist(pts[i], pts[j]);74            if (d < res.d) {75                res.d = d;76                res.p1 = pts[i];77                res.p2 = pts[j];78            }79        }80 81    if (enableTrace) {82        TraceStep step;83        step.type = "base_case";84        step.depth = depth;85        step.divideX = 0;86        for (int i = l; i <= r; i++) step.points.push_back(pts[i]);87        step.currentBest = res;88        step.stripWidth = 0;89        trace.push_back(step);90    }91 92    return res;93}94 95Result stripClosest(vector<Point>& strip, double d, int depth, bool enableTrace) {96    Result res;97    res.d = d;98    sort(strip.begin(), strip.end(), [](Point a, Point b){ return a.y < b.y; });99 100    for (size_t i = 0; i < strip.size(); i++)101        for (size_t j = i+1; j < strip.size() && strip[j].y - strip[i].y < res.d; j++) {102            double dist_ij = dist(strip[i], strip[j]);103            if (dist_ij < res.d) {104                res.d = dist_ij;105                res.p1 = strip[i];106                res.p2 = strip[j];107            }108        }109 110    if (enableTrace && !strip.empty()) {111        TraceStep step;112        step.type = "strip_check";113        step.depth = depth;114        step.divideX = 0;115        step.currentBest = res;116        step.stripPoints = strip;117        step.stripWidth = 2 * d;118        trace.push_back(step);119    }120 121    return res;122}123 124Result closestRec(vector<Point>& pX, vector<Point>& pY, int l, int r, int depth, bool enableTrace) {125    // Use brute force for 3 or fewer points126    if (r - l <= 2) return bruteForce(pX, l, r, depth, enableTrace);127 128    int mid = l + (r-l)/2;129    Point midPt = pX[mid];130 131    // Trace divide step132    if (enableTrace) {133        TraceStep step;134        step.type = "divide";135        step.depth = depth;136        step.divideX = midPt.x;137        for (int i = l; i <= r; i++) step.points.push_back(pX[i]);138        step.currentBest = Result();139        step.stripWidth = 0;140        trace.push_back(step);141    }142 143    // Partition pY into left and right based on midpoint144    vector<Point> lY, rY;145    for (auto& p : pY) {146        if (p.x <= midPt.x) {147            lY.push_back(p);148        } else {149            rY.push_back(p);150        }151    }152 153    // Trace left recursion154    if (enableTrace) {155        TraceStep step;156        step.type = "left_recurse";157        step.depth = depth;158        step.divideX = midPt.x;159        for (int i = l; i <= mid; i++) step.points.push_back(pX[i]);160        step.currentBest = Result();161        step.stripWidth = 0;162        trace.push_back(step);163    }164 165    Result lRes = closestRec(pX, lY, l, mid, depth + 1, enableTrace);166 167    // Trace right recursion168    if (enableTrace) {169        TraceStep step;170        step.type = "right_recurse";171        step.depth = depth;172        step.divideX = midPt.x;173        for (int i = mid + 1; i <= r; i++) step.points.push_back(pX[i]);174        step.currentBest = Result();175        step.stripWidth = 0;176        trace.push_back(step);177    }178 179    Result rRes = closestRec(pX, rY, mid+1, r, depth + 1, enableTrace);180    Result res = (lRes.d < rRes.d) ? lRes : rRes;181 182    // Build strip from current Y-sorted subarray only (not all points)183    // Only include points within distance res.d from the dividing line184    vector<Point> strip;185    for (auto& p : pY) {186        if (abs(p.x - midPt.x) < res.d) {187            strip.push_back(p);188        }189    }190 191    Result stripRes = stripClosest(strip, res.d, depth, enableTrace);192    Result finalRes = (stripRes.d < res.d) ? stripRes : res;193 194    // Trace merge step195    if (enableTrace) {196        TraceStep step;197        step.type = "merge";198        step.depth = depth;199        step.divideX = midPt.x;200        for (int i = l; i <= r; i++) step.points.push_back(pX[i]);201        step.currentBest = finalRes;202        step.stripWidth = 0;203        trace.push_back(step);204    }205 206    return finalRes;207}208 209Result findClosestPair(vector<Point>& pts, bool enableTrace = false) {210    vector<Point> pX = pts, pY = pts;211    sort(pX.begin(), pX.end(), [](Point a, Point b){ return a.x < b.x; });212    sort(pY.begin(), pY.end(), [](Point a, Point b){ return a.y < b.y; });213    return closestRec(pX, pY, 0, pX.size()-1, 0, enableTrace);214}215 216int main(int argc, char* argv[]) {217    string file = (argc > 1) ? argv[1] : "test_data/closest_pair/test_1_n100.txt";218 219    ifstream in(file);220    int n; in >> n;221    vector<Point> pts(n);222    for (int i = 0; i < n; i++) in >> pts[i].x >> pts[i].y;223    in.close();224 225    // Enable trace only for n <= 50226    bool enableTrace = (n <= 50);227    trace.clear();228 229    auto start = chrono::high_resolution_clock::now();230    Result res = findClosestPair(pts, enableTrace);231    auto end = chrono::high_resolution_clock::now();232    double time_ms = chrono::duration<double, milli>(end - start).count();233 234    cout << "Closest Pair (n=" << n << "):\n";235    cout << "P1: (" << res.p1.x << ", " << res.p1.y << ")\n";236    cout << "P2: (" << res.p2.x << ", " << res.p2.y << ")\n";237    cout << "Distance: " << res.d << "\n";238    cout << "Time: " << time_ms << " ms\n";239 240    // Output trace as JSON if enabled241    if (enableTrace && !trace.empty()) {242        cout << "TRACE_START\n";243        cout << "[";244        for (size_t i = 0; i < trace.size(); i++) {245            cout << trace[i].toJSON();246            if (i < trace.size() - 1) cout << ",";247        }248        cout << "]\n";249        cout << "TRACE_END\n";250    }251 252    ofstream out(file.substr(0, file.find_last_of('.')) + "_output.txt");253    out << "Points: " << n << "\nDistance: " << res.d << "\nTime: " << time_ms << " ms\n";254    out.close();255 256    return 0;257}258