Algorithm implementations in C++

Algorithms.md

Algorithm implementations in C++

Convex Hull (Graham Scan Algorithm)

#include <bits/stdc++.h>
using namespace std ;

struct Point{
    int x;
    int y;
};

struct Comparator {
    Point origin;
public:
    Comparator(Point p) {
        this->origin = p;
    }
    
    bool operator()(const Point &a, const Point &b) {
        if(triAngleArea(origin, a, b) == 0) // co linear
            return sqDist(origin,a)<sqDist(origin,b) ;
        double d1x = a.x-origin.x ; double d1y = a.y-origin.y ;
        double d2x = b.x-origin.x ; double d2y = b.y-origin.y ;
        return (atan2(d1y,d1x)-atan2(d2y,d2x))<0;
    }
private:
    int triAngleArea(Point a, Point b, Point c) {
        return (a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));
    }
    int sqDist(Point a, Point b) {
        return ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
    } 
    
};

class ConvexHull {
    Point origin;
    vector<Point> points;
    vector<Point> convexPoints;
public:
    ConvexHull(vector<Point> coordinates) {
        this->points = coordinates;
    } 
    
    vector<Point> getConvexPoints() {
        setOrigin(points);
        sort(next(points.begin()), points.end(), Comparator(origin));
        
        convexPoints = {points[0], points[1], points[2]};
        
        for(int i=3, j=3; i<points.size(); i++){
            while(j>=2 && triAngleArea(convexPoints[j-2], convexPoints[j-1], points[i]) <= 0) {
                convexPoints.pop_back();
                j--;
            }
            convexPoints.push_back(points[i]);
            j++;
        }
        return convexPoints;
    }
    
private:
    //set the left most upper point as origin
    void setOrigin(vector<Point> coordinates) {
        int originIndex = 0;
        for(int i=1; i<coordinates.size(); i++) {
            Point point = coordinates[i];
            Point probableOrigin = coordinates[originIndex];
            if(point.x < probableOrigin.x || (point.x == probableOrigin.x && point.y > probableOrigin.y))
                originIndex = i;
        }
        origin = points[originIndex];
        swap(points[0], points[originIndex]);
    }
    
    int triAngleArea(Point a, Point b, Point c) {
        return (a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));
    }    

};

int main(){
    
    ConvexHull *ch = new ConvexHull({{1,1},{2,2},{1,0},{0,10},{10,10},{3,3}});
    
    vector<Point> convexPoints = ch->getConvexPoints();
    
    for(Point point : convexPoints) {
        cout<<"X: "<<point.x<<" Y: "<<point.y<<endl;
    }
    
    return 0;
}

DSU by rank and path compression

#include<bits/stdc++.h>
using namespace std;

class DSU {
    vector<int> parent;
    vector<int> rank;
public:
    DSU (int nodes) {
        vector<int> temp(nodes);
        parent = temp;
        rank = temp;
        for(int i=0; i<nodes; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    int getParent(int node) {
        if(node == parent[node])
            return node;
        return parent[node] = getParent(parent[node]);
    }
    
    void makeUnion(int a, int b) {
        int pa = getParent(a);
        int pb = getParent(b);
        if(rank[pa] == rank[pb]) {
            parent[pb] = pa;
            rank[pa]++;
        } else {
            if(rank[pa] < rank[pb])
                parent[pa] = pb;
            else parent[pb] = pa;
        }
    }
    
    void printParents() {
        for(int i=0; i<parent.size(); i++) {
            cout<<"Node: "<<i<<" Parent: "<<parent[i]<<endl;
        }
    }
    
};

int main() {
    
    DSU *dsu = new DSU(10);
    
    dsu->makeUnion(1,2);

    dsu->makeUnion(4,5);
    dsu->makeUnion(6,7);
    dsu->makeUnion(5,6);
    
    cout<<dsu->getParent(7)<<endl;
    
    return 0;
}

Visualize_ConvexHull.md