• Maths
• Greedy
• Binary Search (Still learning)
• Number Theory
• Bitwise Operators
• DP
• DFS/BFS
• Segment Trees

• Competitive Programmer’s Handbook by Antti Laaksonen (For Theory)
• CP-Algorithms Website (Link)
• Errichto, acraider and galen_colin's Youtube Channel
• CSES Problem Set (Here)
• CF Problem Set for Practice (Here)

Use the concept of slopes to determine the position of point p3 relative to the line formed by points P1 and P2.

Calculate the slopes m1 and m2 for line segments P1P2 and P2P3 respectively.

cout << (m2 > m1 ? "LEFT" : (m2 < m1 ? "RIGHT" : "TOUCH")) << "\n";

Try to interprete this geometrically

void solve()
{
    ll x1,y1,x2,y2,x3,y3;
    cin>>x1>>y1>>x2>>y2>>x3>>y3;

    ll m1 = (y2-y1)*(x3-x2); //Slope for P1P2
    ll m2 = (y3-y2)*(x2-x1); //Slope for P2P3

    if (m2 > m1) //Slope of P2P3 is greater than P1P2 means P3 is lies on the left of the given line segment
    {
        cout<<"LEFT"<<"\n";
    }
    else if (m2 < m1) //Slope of P1P2 is greater than P2P3 means P3 is lies on the right of the given line segment
    {
        cout<<"RIGHT"<<"\n";
    }
    else //Slope of both line segments is zero. Hence, point P3 lies on the given line segment
    {
        cout<<"TOUCH"<<"\n";
    }
}

Use the concept of orientation of three points.

• If the orientations of the endpoints of one line segment are different from the orientations of the endpoints of the other line segment, then they intersect.
• If the orientation of one line segment is 0 (collinear) and the corresponding point lies on the other line segment, then they intersect.
• If none of the above conditions are met, then the line segments do not intersect.

// Function to calculate the orientation of three points
ll getOrientation(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3)
{
    // Calculate the value using cross product of vectors
    ll val = (x3 - x2) * (y2 - y1) - (x2 - x1) * (y3 - y2);

    // Check the value to determine the orientation
    if (val > 0) {
        return 1; // Clockwise orientation
    }
    else if (val < 0) {
        return 2; // Counterclockwise orientation
    }
    return 0;  // Collinear orientation
}

// Function to check if a point lies on a line segment
bool isOnSegment(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3)
{
    // Check if the point (x3, y3) lies within the range of (x1, y1) and (x2, y2) coordinates
    return ((x3 <= max(x1, x2)) && (x3 >= min(x1, x2)) && (y3 <= max(y1, y2)) && (y3 >= min(y1, y2)));
}

void solve()
{
    // Read the coordinates of the line segments
    ll x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

    // Calculate the orientations for all possible combinations of endpoints
    ll orientation1 = getOrientation(x1, y1, x2, y2, x3, y3);
    ll orientation2 = getOrientation(x1, y1, x2, y2, x4, y4);
    ll orientation3 = getOrientation(x3, y3, x4, y4, x1, y1);
    ll orientation4 = getOrientation(x3, y3, x4, y4, x2, y2);

    // Check if the line segments intersect based on orientations and point lies on segments
    if ((orientation1 != orientation2) && (orientation4 != orientation3))
    {
        cout << "YES" << "\n"; // Line segments intersect
    }
    else if (orientation1 == 0 && isOnSegment(x1, y1, x2, y2, x3, y3))
    {
        cout << "YES" << "\n"; // Collinear point lies on the line segment
    }
    else if (orientation2 == 0 && isOnSegment(x1, y1, x2, y2, x4, y4))
    {
        cout << "YES" << "\n"; // Collinear point lies on the line segment
    }
    else if (orientation3 == 0 && isOnSegment(x3, y3, x4, y4, x1, y1))
    {
        cout << "YES" << "\n"; // Collinear point lies on the line segment
    }
    else if (orientation4 == 0 && isOnSegment(x3, y3, x4, y4, x2, y2))
    {
        cout << "YES" << "\n"; // Collinear point lies on the line segment
    }
    else
    {
        cout << "NO" << "\n"; // Line segments do not intersect
    }
}

Do you know about Shoelace formula? (also known as Gauss's area formula).

void solve() {
    ll n;
    cin >> n;
    vector<pair<ll, ll>> coordinates;

    // Read the coordinates of the vertices
    for (ll i = 0; i < n; ++i) {
        ll x, y;
        cin >> x >> y;
        coordinates.push_back({x, y});
    }

    ll area = 0;
    // Calculate the area using the Shoelace formula
    for (ll i = 0; i < n; ++i) {
        ll x1 = coordinates[i].first;
        ll y1 = coordinates[i].second;

        ll x2 = coordinates[(i + 1) % n].first;
        ll y2 = coordinates[(i + 1) % n].second;

        // Add the product of current and next vertex coordinates to the area
        area += ((x1 * y2) - (x2 * y1));
    }

    // Take the absolute value of the area
    area = abs(area);

    // Print the result: 
    cout << area << "\n";
}

For a given point draw a line from the point itself to infinity in some direction and keep track of the number of intersections with polygon edges and try to draw some conclusions.

If it intersects the edges of polygon odd number of times, then the point lies inside the polygon otherwise outside the polygon.

// Function to determine the orientation of three points (Clockwise, Counter-Clockwise, Collinear)
ll getOrientation(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
    ll value = (x3 - x2) * (y2 - y1) - (x2 - x1) * (y3 - y2);
    if (value > 0) {
        return 1; // Clockwise
    } else if (value < 0) {
        return 2; // Counter-Clockwise
    } else {
        return 0; // Collinear
    }
}

// Function to check if a point lies on a line segment
bool isOnSegment(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
    return ((x3 <= max(x1, x2)) && (x3 >= min(x1, x2)) && (y3 <= max(y1, y2)) && (y3 >= min(y1, y2)));
}

// Function to check if two line segments intersect
bool intersect(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c, pair<ll, ll> d) {
    ll x1 = a.first;
    ll y1 = a.second;
    ll x2 = b.first;
    ll y2 = b.second;
    ll x3 = c.first;
    ll y3 = c.second;
    ll x4 = d.first;
    ll y4 = d.second;

    ll orientation1 = getOrientation(x1, y1, x2, y2, x3, y3);
    ll orientation2 = getOrientation(x1, y1, x2, y2, x4, y4);
    ll orientation3 = getOrientation(x3, y3, x4, y4, x1, y1);
    ll orientation4 = getOrientation(x3, y3, x4, y4, x2, y2);

    if (orientation1 != orientation2 && orientation3 != orientation4) {
        return true; // Segments intersect
    }
    return false; // Segments do not intersect
}
void solve() {
    ll n, m;
    cin >> n >> m;

    vector<pair<ll, ll>> vertices;
    for (ll i = 0; i < n; ++i) {
        ll x, y;
        cin >> x >> y;
        vertices.push_back({x, y});
    }

    vector<pair<ll, ll>> points;
    for (ll i = 0; i < m; ++i) {
        ll x, y;
        cin >> x >> y;
        points.push_back({x, y});
    }

    for (auto curPoint : points) {
        pair<ll, ll> endpoint = make_pair(INT_MAX, INT_MAX + 1ll);
        ll intersectCount = 0;
        bool boundary = false;

        // Check each line segment of the polygon
        for (ll i = 0; i < n; ++i) {
            pair<ll, ll> a = vertices[i];
            pair<ll, ll> b = vertices[(i + 1) % n];

            // Check if the point lies on the current line segment
            if (getOrientation(a.first, a.second, b.first, b.second, curPoint.first, curPoint.second) == 0 &&
                isOnSegment(a.first, a.second, b.first, b.second, curPoint.first, curPoint.second)) {
                boundary = true; // Point lies on the boundary
                break;
            }

            // Check if the line segment intersects with the ray from the current point
            if (intersect(a, b, curPoint, endpoint)) {
                intersectCount++; // Increment intersection count
            }
        }

        // Determine the location of the point
        if (boundary) {
            cout << "BOUNDARY" << "\n";
        } else if (intersectCount % 2) {
            cout << "INSIDE" << "\n";
        } else {
            cout << "OUTSIDE" << "\n";
        }
    }
}

Use the given side lengths to calculate the area of the hexagon.

void solve()
{
    // Read the side lengths of the hexagon
    ll a1, a2, a3, a4, a5, a6;
    cin >> a1 >> a2 >> a3 >> a4 >> a5 >> a6;

    // Calculate the area of the hexagon using the given side lengths
    // Formula: (a1 + a2 + a3)^2 - a1^2 - a3^2 - a5^2
    ll hexagonArea = (a1 + a2 + a3) * (a1 + a2 + a3) - (a1 * a1) - (a3 * a3) - (a5 * a5);

    // Determine the number of small triangles by dividing the hexagon area by 1
    ll numOfTriangles = hexagonArea / 1;

    cout << numOfTriangles << "\n";
}

Maria can only fall into the water if she makes a left turn.

void solve()
{
    ll n;
    cin >> n; // Read the number of straight sections from the input

    ll temp = n;
    temp++;

    vector<pair<ll,ll>> vp;
    while(temp--)
    {
        ll x, y;
        cin >> x >> y; // Read the coordinates of each point on the track
        vp.push_back({x, y}); // Store the coordinates in a vector
    }

    ll cnt = 0; // Initialize a variable to count the number of dangerous turns

    for (ll i = 1; i < n-1; ++i)
    {
        // Check the directions to determine if the turn is left and dangerous

        if (vp[i].first > vp[i-1].first && vp[i+1].second > vp[i].second)
        {
            cnt++; // Increment the count if the turn is left
        }
        else if (vp[i].first < vp[i-1].first && vp[i+1].second < vp[i].second)
        {
            cnt++; // Increment the count if the turn is left
        }
        else if (vp[i].second > vp[i-1].second && vp[i+1].first < vp[i].first)
        {
            cnt++; // Increment the count if the turn is left
        }
        else if (vp[i].second < vp[i-1].second && vp[i+1].first > vp[i].first)
        {
            cnt++; // Increment the count if the turn is left
        }
    }

    cout << cnt << "\n"; // Print the count of dangerous turns
}

Let's consider the number of inner corners of 270 degrees as x, and the number of inner corners of 90 degrees as n-x. The sum of the inner angles of a polygon with n vertices is equal to 180 * (n-2) degrees.. Since each inner corner of 270 degrees contributes 270 degrees to the sum, and each inner corner of 90 degrees contributes 90 degrees, we can write it as:

x * 270 + (n-x) * 90 = 180 * (n-2)

270x + 90n-90x = 180n-360

180x = 90n-360

2x = n-4

x = (n-4) / 2

So, the number of dangerous turns (the number of inner corners of 270 degrees) is (n-4) / 2. This allows us to calculate the answer in constant time complexity, O(1).

void solve()
{
    ll n;
    cin>>n;
    cout<<(n-4)/2<<"\n";
}

• Check if the segment is vertical or horizontal
• Check if any coordinate pair has a count of 2 (indicating a vertex)

1. Count of both vertical and horizontal segments should be 2
2. Number of distinct vertices should be 4

void solve()
{
    ll x1, y1, x2, y2;
    map<pair<ll, ll>, ll> pointCount;
    ll verticalSegments = 0, horizontalSegments = 0;
    ll distinctVertices = 0;

    // Process the segments
    for (ll i = 0; i < 4; ++i)
    {
        cin >> x1 >> y1 >> x2 >> y2;

        // Check if the segment is vertical or horizontal
        if (x1 == x2 && y1 != y2) {
            verticalSegments++;
        }
        if (x1 != x2 && y1 == y2) {
            horizontalSegments++;
        }

        // Increment the count of the coordinate pairs
        pointCount[{x1, y1}]++;
        pointCount[{x2, y2}]++;

        // Check if any coordinate pair has a count of 2 (indicating a vertex)
        if (pointCount[{x1, y1}] == 2) {
            distinctVertices++;
        }
        if (pointCount[{x2, y2}] == 2) {
            distinctVertices++;
        }
    }

    // Check the conditions for forming a rectangle
    if (verticalSegments == 2 && horizontalSegments == 2 && distinctVertices == 4 && pointCount.size() == 4)
    {
        cout << "YES" << "\n";
    }
    else
    {
        cout << "NO" << "\n";
    }
}

• The diagonals of a parallelogram split each other in the middle.

void solve(){
        int n;
        cin>>n;

        int x[n];
        int y[n];

        for(int i=0;i<n;i++){
                cin>>x[i]>>y[i];
        }

        map<pair<int,int>,int>mp;
        for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++){

                        // division by 2 is ignored, to get rid of doubles
                        int mid_x=x[i]+x[j];
                        int mid_y=y[i]+y[j];


                        // increase the frequency of mid point
                        mp[make_pair(mid_x,mid_y)]++;
                }
        }

        int ans=0;
        for(auto it:mp){
                int freq = it.second;
                ans += (freq*(freq-1))/2;
        }

        cout<<ans;
}

• Intersection of any number of rectangles is a always a rectangle.

• While iterating through each rectangle, try to find the overlapping region of remaining (n-1) regions.

void solve() {
    int n;
    cin >> n;

    multiset<int> LeftX;
    multiset<int> LeftY;
    multiset<int> RightX;
    multiset<int> RightY;

    //store the coordinates of the rectangles
    vector<pair<int, int>> X(n);
    vector<pair<int, int>> Y(n);

    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        X[i].first = x1;
        X[i].second = x2;
        Y[i].first = y1;
        Y[i].second = y2;

        LeftX.insert(x1);
        LeftY.insert(y1);
        RightX.insert(x2);
        RightY.insert(y2);
    }

    // Iterate through each rectangle and find the point that belongs to (n-1) rectangles
    for (int i = 0; i < n; i++) {
        int x1, x2, y1, y2;
        x1 = X[i].first;
        x2 = X[i].second;
        y1 = Y[i].first;
        y2 = Y[i].second;

        // Temporarily remove the current rectangle from the sets
        LeftX.erase(LeftX.find(x1));
        RightX.erase(RightX.find(x2));
        LeftY.erase(LeftY.find(y1));
        RightY.erase(RightY.find(y2));

        // Find the extreme x and y coordinates among the remaining rectangles
        int X1 = *LeftX.rbegin();
        int X2 = *RightX.begin();
        int Y1 = *LeftY.rbegin();
        int Y2 = *RightY.begin();

        // Check if there is an overlap between the extreme x and y coordinates
        if (X1 <= X2 && Y1 <= Y2) {
            // If an overlap exists, print the coordinates and return
            cout << X1 << " " << Y1 << endl;
            return;
        }

        // Restore the removed values back to the sets
        LeftX.insert(x1);
        RightX.insert(x2);
        LeftY.insert(y1);
        RightY.insert(y2);
    }
}

For each unvisited cell, do the DFS (or BFS) traversal and keep the track of count

ll n,m;
char arr[1011][1011];
bool vis[1011][1011];

void dfs(ll i, ll j)
{
    //Check Base Conditions
    if ((i < 0) || (j < 0) || (i >= n) || (j >= m) || vis[i][j]==true || arr[i][j]=='#'){
        return;
    }
    //Mark the visited cell as True
    vis[i][j] = true;
    //Try to explore in all 4 possible directions
    dfs(i-1,j);
    dfs(i+1,j);
    dfs(i,j-1);
    dfs(i,j+1);
}
void solve()
{   
    ll ans = 0;
    cin>>n>>m;
    rep(i,0,n){
        rep(j,0,m){
            cin>>arr[i][j];
        }
    }
    //Initially mark all cells as unvisited
    memset(vis,false,sizeof(vis));
    for (ll i = 0; i < n; ++i){
        for (ll j = 0; j < m; ++j){
            if (!vis[i][j] && arr[i][j]=='.') //If current cell is unvisited and belongs to '.'(floor){
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

Do the traversal from A to B and simultaneously store the directions in the array

For the traversal, you have to use BFS only. Why ?

ll n,m;
char arr[1011][1011];
bool vis[1011][1011];
ll prev_step[1011][1011];
ll dx[4]={-1,0,1,0};
ll dy[4]={0,1,0,-1};
string directions="URDL";


void solve()
{   
    cin>>n>>m;

    //Mark all unvisited cells as false
    memset(vis,false,sizeof(vis));


    queue<pair<ll,ll>> q;
    pair<ll,ll> begin;
    pair<ll,ll> end;

    rep(i,0,n){
        rep(j,0,m){
            cin>>arr[i][j];
            //Store the index of starting node and ending node
            if(arr[i][j]=='A'){
                begin=make_pair(i,j);
            }
            else if(arr[i][j]=='B'){
                end=make_pair(i,j);
            }
            
        }
    }



    q.push(begin);
    vis[begin.first][begin.second]=true;

    while(!q.empty()){
        pair<ll,ll> temp=q.front();
        q.pop();
        for(ll i=0;i<4;i++){
            pair<ll,ll> ok = make_pair(temp.first+dx[i],temp.second+dy[i]);

            //Base Cases
            if (ok.first<0 || ok.first>=n || ok.second<0 || ok.second>=m){
                continue;
            }
            if (arr[ok.first][ok.second]=='#'){
                continue;
            }
            if (vis[ok.first][ok.second]){
                continue;
            }


            //Mark the current cell as visited and store the directions
            vis[ok.first][ok.second] = true;
            prev_step[ok.first][ok.second] = i;
            q.push(ok);
        }
    }


    //If the ending node is visited, then there is exists a path between starting node and ending node
    if (vis[end.first][end.second])
    {
        cout<<"YES"<<"\n";
        vector<ll>steps;

        while(end != begin){
            ll ok1 = prev_step[end.first][end.second];
            steps.push_back(ok1);
            end=make_pair(end.first-dx[ok1], end.second-dy[ok1]);
        }

        reverse(steps.begin(), steps.end());

        cout<<steps.size()<<"\n";

        for(auto it:steps){
            cout<<directions[it];
        }
        cout<<endl;
        
    }
    //If ending node is not visited, there does not exist any path 
    else
    {
        cout<<"NO"<<"\n";
        return;
    }
}

If there are k connected components, then minimum number of roads required is (k-1)

Do DFS traversal on all unvisited nodes and store one node from each connected component

ll n,m;
vector<ll> adj[200001];
vector<bool>vis(200001);
vector<ll>paths;

void dfs(int node)
{
    vis[node]=true;
    for(auto it:adj[node]){
        if(!vis[it]){
            dfs(it);
        }
    }
}

void solve()
{   
    cin>>n>>m;
    while(m--){
        ll a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
     
    fill(vis.begin(),vis.end(),false);
    
    for (ll i = 1; i <= n; ++i)
    {
        if (!vis[i])
        {
            //Saving one node from each connected component
            paths.push_back(i);
            dfs(i);
        }
    }

    cout<<paths.size()-1<<endl;
    
    for(ll i=1;i<paths.size();i++){
        cout<<paths[i]<<" "<<paths[i]-1<<endl;;
    }

}

This is same as second problem

You can't do DFS traversal. Think why ?

• Do the BFS traversal from start node
• If target node is found in the path, stop there and store all the nodes from target node to start that occurred in the path

void bfs(vector<ll>adj[], int start, int end)
{
    vector<ll> ans; //To store the path
    bool vis[end+20];
    vector<ll> temp(end+20);
    temp[start]=-1;     
    memset(vis,false,sizeof(vis)); 

    vis[start] = true;

    queue<ll>q;
    q.push(start);

    while(!q.empty()){
        ll ok = q.front();
        for(auto it:adj[ok]){
            if(!vis[it]){
                vis[it]=true;
                temp[it]=ok;
                q.push(it);
            }
        }
        q.pop();
    }
    if (vis[end]){ //If end node is visited, it means there exist a path
        for(ll i=end; i!=-1; i=temp[i]){
            ans.push_back(i+1);
        }
    }

    reverse(ans.begin(),ans.end());

    if (ans.empty())
    {
        cout<<"IMPOSSIBLE"<<"\n";
        return;
    }

    cout<<ans.size()<<endl;
    for(auto it:ans){
        cout<<it<<" ";
    } 
}

void solve()
{   
    ll n,m;
    cin>>n>>m;
    vector<ll> adj[n+1];
    while(m--){
         ll a,b;
         cin>>a>>b;
         a--;b--;
         adj[a].push_back(b);
         adj[b].push_back(a);
    }
    //Do the BFS traversal from start node to end node
    bfs(adj,0,n-1);
}

We can use a graph coloring algorithm

The idea is to assign a color to each pupil in such a way that no two consecutive friends are assigned the same color.

ll n,m;
vector<vector<ll>>adj ;
vector<bool>vis;
vector<ll>ok(100001); //To store the colors

bool dfs(ll curNode, ll color)
{
    //Mark the current node as visited and assign the color
    vis[curNode] = true;
    ok[curNode] = color;

    for(auto it:adj[curNode]){
        if (!vis[it])
        {
            bool temp = dfs(it,color^1); //XOR the current color with 1 to change it from adjacent node's color
            if (temp==false)
            {
                return false;
            }
            else
            {
                if (ok[curNode] == ok[it])
                {
                    return false;
                }
            }
        }
    }
    return true;
}

void solve()
{
    cin>>n>>m;

    adj.assign(n+1,{});
    vis.assign(n+1,false);

    while(m--){
        ll a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    bool check = true;

    for (ll i = 1; i <= n; ++i){
        if (!vis[i]) //If the given node is unvisited, perform dfs travesal
        {
            check = dfs(i,0);
            if (!check){
                break;
            }
        }
    }

    if (!check){
        cout<<"IMPOSSIBLE"<<"\n";
        return;
    }

    //Print the color given to each pupil
    for (int i = 1; i <= n; ++i){
        cout<<ok[i]+1<<" ";
    }
    cout<<endl;
    
}

Just try to find the cycle in the graph. That's it. That's is the solution !

ll n,m;
ll start,en;
vector<vector<ll>>adj;
vector<bool>vis;
vector<ll>parent;


bool dfs(ll curNode, ll curParent)
{
    vis[curNode] = true;
    parent[curNode] = curParent;

    for(auto it:adj[curNode]){
        if(it==curParent){
            continue;
        }
        if(vis[it]){
            start = it;
            en = curNode;
            return true;
        }
        if (!vis[it]){
            if (dfs(it,curNode)){
                return true;
            }
        }
    }
    return false;
}

bool visit_all()
{
    for (ll i = 1; i <= n; ++i){
        if (!vis[i]){
            if (dfs(i,-1)){
                return true;
            }
        }
    }
    return false;
}

void solve()
{
    cin>>n>>m;

    adj.assign(n+1,{});
    vis.assign(n+1,false);
    parent.resize(n+1);

    rep(i,0,m){
        ll a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    if (!visit_all())   
    {
        cout<<"IMPOSSIBLE"<<"\n";
        return;
    }
    ll ok = en;
    vector<ll> cycle;
    cycle.push_back(en);
    while(ok != start){
        cycle.push_back(parent[ok]);
        ok = parent[ok];
    }
    cycle.push_back(en);
    cout<<cycle.size()<<"\n";
    for(auto it:cycle){
        cout<<it<<" ";
    }
    cout<<endl;

}