Collinear Checking

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

int main(){
  int n;
  cin>>n;
  int points[n][2];
  for(int i=0;i<n;i++){
    cin>>points[i][0]>>points[i][1];
  }
  int slopes[n];
  for(int i=0;i<n-1;i++){
    int x1=points[i][0];
    int y1=points[i][1];
    int x2=points[i+1][0];
    int y2=points[i+1][1];
    int slope = (y2-y1)/(x2-x1);
    slopes[i]=slope;
    }
  sort(slopes,slopes+n-1);
  if(n==1){
    cout<<"Yes"<<endl;
  }
  else
  {
  if(slopes[0] == slopes[n-2]){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  }
}

Minimizing Manhattan Distance

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

int main(){
  cout<<"Enter the number of points" <<endl;
  int n;
  cin>>n;
  int points[n][2];
  for(int i=0;i<n;i++){
    cin>>points[i][0]>>points[i][1];
  }
  int maxindex = -1;
  int minindex = -1;
  int maxsum = points[0][0]+points[0][1];
  int maxdiff = points[0][0]-points[0][1];
  int minsum = points[0][0]+points[0][1];
  int mindiff = points[0][0]-points[0][1];

  for(int i=0;i<n;i++){
   int sum = points[i][0]+points[i][1];
   int diff = points[i][0]-points[i][1];
  if(sum>maxsum){
    maxsum=sum;
    maxindex = i;
  }
  if(sum<minsum){
    minsum=sum;
    /*maxindex = i;*/
  }
  if(diff>maxdiff){
    maxdiff=diff;
   minindex = i;
  }
  if(diff<mindiff){
    mindiff=diff;
   /*minindex = i; */
  }
  }
  int max_distance = max(maxsum-minsum,maxdiff-mindiff);
  /*cout<<"Maximum Manhattan distance is: "<<max_distance<<endl;  */
  /*cout<<maxindex<<" "<<minindex<<endl;  */

  int max_distances_array[n-1];

  int maxsum2 = points[0][0]+points[0][1];
  int maxdiff2 = points[0][0]-points[0][1];
  int minsum2 = points[0][0]+points[0][1];
  int mindiff2 = points[0][0]-points[0][1];

  for(int i=0;i<n;i++){
    if(i==maxindex){
      continue;
    }
    int sum = points[i][0]+points[i][1];
    int diff = points[i][0]-points[i][1];
    if(sum>maxsum2){
      maxsum2=sum;
    }
    if(sum<minsum2){
      minsum2=sum;
    }
    if(diff>maxdiff2){
      maxdiff2=diff;
    }
    if(diff<mindiff2){
      mindiff2=diff;
    }


  }
  int max_1 = max(maxsum2-minsum2,maxdiff2-mindiff2);



  int maxsum3 = points[0][0]+points[0][1];
  int maxdiff3 = points[0][0]-points[0][1];
  int minsum3 = points[0][0]+points[0][1];
  int mindiff3 = points[0][0]-points[0][1];

  for(int i=0;i<n;i++){
    if(i==minindex){
      continue;
    }
    int sum = points[i][0]+points[i][1];
    int diff = points[i][0]-points[i][1];
    if(sum>maxsum3){
      maxsum3=sum;
    }
    if(sum<minsum3){
      minsum3=sum;
    }
    if(diff>maxdiff3){
      maxdiff3=diff;
    }
    if(diff<mindiff3){
      mindiff3=diff;
    }
  }
  int max_2 = max(maxsum3-minsum3,maxdiff3-mindiff3);

  int min_1 = min(max_1,max_2);
  cout<<min_1<<endl;
}

Internal points inside Polygon

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

int rectangleArea(vector<pair<int, int>> points) {
  int baseLength;
  if (points[0].first == points[1].first) {
    baseLength = abs(points[0].second - points[1].second);
  } else {
    baseLength = abs(points[0].first - points[1].first);
  }
  int height;
  if (points[1].first == points[2].first) {
    height = abs(points[1].second - points[2].second);
  } else {
    height = abs(points[1].first - points[2].first);
  }
  return baseLength * height;
}

int integralPoints(vector<pair<int, int>> points, int area) {
  int side1 = __gcd(abs(points[0].first - points[1].first),
                    abs(points[0].second - points[1].second));
  int side2 = __gcd(abs(points[1].first - points[2].first),
                    abs(points[1].second - points[2].second));
  int side3 = __gcd(abs(points[2].first - points[0].first),
                    abs(points[2].second - points[0].second));
  int boundary = side1 + side2 + side3;
  int internal = area - boundary / 2 + 1;
  return internal + boundary;
}

int triangleArea(vector<pair<int, int>> points) {
  return abs((points[0].first * (points[1].second - points[2].second) +
              points[1].first * (points[2].second - points[0].second) +
              points[2].first * (points[0].second - points[1].second)) /
             2);
}

int integralPointsRectangle(vector<pair<int, int>> points) {
  int baseLength;
  if (points[0].first == points[1].first) {
    baseLength = abs(points[0].second - points[1].second);
  } else {
    baseLength = abs(points[0].first - points[1].first);
  }
  int height;
  if (points[1].first == points[2].first) {
    height = abs(points[1].second - points[2].second);
  } else {
    height = abs(points[1].first - points[2].first);
  }
  int area = (baseLength + 1) * (height + 1);
  int internal = area - 2 * (baseLength + height);
  return internal;
}

int main() {
  string s;
  string s2;
  cin>>s>>s2;
  vector<pair<int, int>> points(4);
  for (int i = 0; i < 4; i++) {
    cin >> points[i].first >> points[i].second;
  }

  vector<pair<int, int>> internal(3);
  string s1;
  string s3;
  cin>>s1>>s3;
  for (int i = 0; i < 3; i++) {
    cin >> internal[i].first >> internal[i].second;
  }

  int area = rectangleArea(points);
  int area1 = triangleArea(internal);
  /**/
  /*cout << "The area of the rectangle is " << area << endl;*/
  /*cout << "The area of the triangle is " << area1 << endl;*/
  /*cout << "The remaining area is" << area - area1 << endl;*/
  /**/
  int integralRectangle;
  integralRectangle = integralPointsRectangle(points);
  /*cout << "The number of integral points in the rectangle is "*/
  /*     << integralRectangle << endl;*/
  /**/
  /*cout << "The number of integral points in the triangle is "*/
  /*     << integralPoints(internal, area1) << endl;*/
  /**/
  cout << "Usable area : " << area - area1 << endl;
  cout << "Usable interior points : "
       << integralRectangle - integralPoints(internal, area1) << endl;
}

Circumcircle and Circumcenter of triangle

#include <iostream>
#include <cfloat>
using namespace std;


#define pdd pair<double, double>


void lineFromPoints(pdd P, pdd Q, double &a,
						double &b, double &c)
{
	a = Q.second - P.second;
	b = P.first - Q.first;
	c = a*(P.first)+ b*(P.second);
}


void perpendicularBisectorFromLine(pdd P, pdd Q,
				double &a, double &b, double &c)
{
	pdd mid_point = make_pair((P.first + Q.first)/2,
							(P.second + Q.second)/2);

	c = -b*(mid_point.first) + a*(mid_point.second);

	double temp = a;
	a = -b;
	b = temp;
}

pdd lineLineIntersection(double a1, double b1, double c1,
						double a2, double b2, double c2)
{
	double determinant = a1*b2 - a2*b1;
	if (determinant == 0)
	{
		return make_pair(FLT_MAX, FLT_MAX);
	}

	else
	{
		double x = (b2*c1 - b1*c2)/determinant;
		double y = (a1*c2 - a2*c1)/determinant;
		return make_pair(x, y);
	}
}

void findCircumCenter(pdd P, pdd Q, pdd R)
{
	double a, b, c;
	lineFromPoints(P, Q, a, b, c);

	double e, f, g;
	lineFromPoints(Q, R, e, f, g);

	perpendicularBisectorFromLine(P, Q, a, b, c);
	perpendicularBisectorFromLine(Q, R, e, f, g);

	pdd circumcenter =
		lineLineIntersection(a, b, c, e, f, g);

	if (circumcenter.first == FLT_MAX &&
		circumcenter.second == FLT_MAX)
	{
		cout << "The two perpendicular bisectors "
				"found come parallel" << endl;
		cout << "Thus, the given points do not form "
				"a triangle and are collinear" << endl;
	}

	else
	{
		cout << "The circumcenter of the triangle PQR is: ";
		cout << "(" << circumcenter.first << ", "
			<< circumcenter.second << ")" << endl;
	}
}

int main()
{
	pdd P = make_pair(6, 0);
	pdd Q = make_pair(0, 0);
	pdd R = make_pair(0, 8);
	findCircumCenter(P, Q, R);
	return 0;
}

Largest Area of Square inside 2 Rectangles

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

int main() {
  string s1, s2, s3, s4;
  int n = 3;
  int bottom[n][2];
  int top[n][2];
  cin >> s1 >> s2;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> bottom[i][j];
    }
  }
  cin >> s3 >> s4;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> top[i][j];
    }
  }
  int max_area = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j) {
        int x1 = max(bottom[i][0], bottom[j][0]);
        int y1 = max(bottom[i][1], bottom[j][1]);
        int x2 = min(top[i][0], top[j][0]);
        int y2 = min(top[i][1], top[j][1]);
        int square_side = min(x2 - x1, y2 - y1);
        if (x1 < x2 && y1 < y2) {
          max_area = max(max_area, square_side * square_side);
        }
      }
    }
  }
  cout << max_area << endl;
}

Minimum squares to evenly cut a rectangle

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

int main() {
  int l, w;
  string s1, s2;
  cin >> s1;
  cin >> l;
  cin >> s2;
  cin >> w;
  int area = l * w;
  int count = INT_MAX;
  for (int i = area; i > 0; i--) {
    if (sqrt(i) == floor(sqrt(i))) {
      if (area % i == 0) {
        if (area / i < count) {
          count = area / i;
        }
      }
    }
  }
  cout << count << endl;
}

Happy Prefix

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

int main() {
  string s;
  /*cout << "Enter ur stttirng " << endl;*/
  cin >> s;
  s=s.substr(2,s.size()-2);
  int lps[s.size()];
  lps[0] = 0;
  int len = 0;
  int i = 1;
  while (i < s.size()) {
    if (s[i] == s[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  /*for (int i = 0; i < s.size(); i++) {*/
  /*  cout << lps[i] << " ";*/
  /*}*/
  for (int i = 0; i < lps[s.size() - 1]; i++) {
    cout << s[i];
  }
}

Bit Manipulation (Number of Set Bits)

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

unsigned int countSetBits(unsigned int n)
{
	unsigned int count = 0;
	while (n) {
		count += n & 1;
		n >>= 1;
	}
	return count;
}

int main()
{
	int i = 9;
	cout << countSetBits(i);
	return 0;
}

Robin Karp Algorithm

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

#define d 256

/* pat -> pattern
	txt -> text
	q -> A prime number
*/
void search(char pat[], char txt[], int q)
{
	int M = strlen(pat);
	int N = strlen(txt);
	int i, j;
	int p = 0; // hash value for pattern
	int t = 0; // hash value for txt
	int h = 1;

	for (i = 0; i < M - 1; i++)
		h = (h * d) % q;

	for (i = 0; i < M; i++) {
		p = (d * p + pat[i]) % q;
		t = (d * t + txt[i]) % q;
	}

	for (i = 0; i <= N - M; i++) {

		if (p == t) {
			/* Check for characters one by one */
			for (j = 0; j < M; j++) {
				if (txt[i + j] != pat[j]) {
					break;
				}
			}


			if (j == M)
				cout << "Pattern found at index " << i
					<< endl;
		}

		if (i < N - M) {
			t = (d * (t - txt[i] * h) + txt[i + M]) % q;

			// We might get negative value of t, converting
			// it to positive
			if (t < 0)
				t = (t + q);
		}
	}
}

int main()
{
	char txt[] = "GEEKS FOR GEEKS";
	char pat[] = "GEEK";

	int q = INT_MAX;

	search(pat, txt, q);
	return 0;
}