Cyrus-Beck Algorithm Implementation

#include <bits/stdc++.h>

using namespace std;

#define pii pair<double, double>

vector<pii> vertices,normal;

int n;
double tE, tL;


// Function to calculate dot product
double dot_product(pii A, pii B)
{
    return (A.first*B.first + A.second*B.second);
}

// Operator overloading for Calculation among points

pii operator - (const pii &A, const pii &B)
{
    return make_pair(A.first-B.first, A.second-B.second);
}

pii operator + (const pii &A, const pii &B){
  return make_pair(A.first+B.first, A.second+B.second);
}

// Operator overloading for multiplying a value to a point
pii operator * (const pii &A, const double t){
  return make_pair(t*A.first, t*A.second);
}

// Function to compute Normal
void compute_normal()
{
    pii prev = vertices[0];
    for(int i=1; i<n; i++)
    {
        normal[i-1].second = -1 * (prev.first-vertices[i].first);
        normal[i-1].first = prev.second-vertices[i].second;
        prev = vertices[i];
    }
    normal[n-1].second = -1* (prev.first-vertices[0].first);
    normal[n-1].first = prev.second-vertices[0].second;
}

// Function to check whether the line intersects or not

int check(pii A, pii B)
{
    pii p = B - vertices[0];
    double d1 = dot_product(p, normal[0]);
    pii q = A - vertices[0];
    double d2 = dot_product(q, normal[0]);
    if(d1<0&&d2<0)
      return 1;
    // If the line doesn't intersect
    if(d1>=0&&d2>=0)
      return 0;
    return -1;
}

// Function to Clip
void Clip(pii A, pii B)
{
    tE = 0; tL = 1;
    for(int i=0; i<n; ++i)
    {
        double d = dot_product((B-A), normal[i]);
        if(d==0)
            continue;
        double t = dot_product(A-(vertices[i]), normal[i])/dot_product((A-B),normal[i]);
        //cout<<dot_product(A-(vertices[i]), normal[i])<<" "<<dot_product((A-B), normal[i])<<endl;
        //cout<<d<<"  =  "<<t<<endl<<endl;
        if(d<0&&t>tE)
            tE = t;
        else if(d>0&&t<tL)
            tL = t;
    }
}

int main()
{
    cout<<"Enter the number of vertices\n";
    cin>>n;
    vertices.resize(n);
    normal.resize(n);
    cout<<"Enter the coordinates of the vertices in order\n";
    for(int i=0; i<n; ++i)
    {
        cin>>vertices[i].first>>vertices[i].second;
    }

    sort(vertices.begin(), vertices.end());

    cout<<"Enter the co-ordinates of the line \n";
    pii A, B;
    cin>>A.first>>A.second>>B.first>>B.second;

    compute_normal();
    int chk = check(A, B);
    //cout<<chk<<endl;
    if(chk==-1)
    {
        Clip(A, B);
        //cout<<tE<<" "<<tL;
        if(tE>tL)
            chk = 0;
        else
        {
            pii E = A + (B-A)*tE;
            pii L = A + (B-A)*tL;
            //cout<<tE<<", "<<tL;
            cout<<"\n("<<E.first<<", "<<E.second<<"), ("<<L.first<<", "<<L.second<<")";
        }
    }
    if(chk==1)
    cout<<"\nNo Clipping Points Found";

//    for(int j=0; j<normal.size(); j++)
//    {
//        cout<<normal[j].first<<", "<<normal[j].second<<endl;
//    }

    return 0;
}