Geometric Algorithms
Geometric Algorithms
6 Area of a Hexagon 45
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1
Contents
24 Check if a given circle lies completely inside the ring formed by two
concentric circles 138
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
25 Check if a line at 45 degree can divide the plane into two equal weight
parts 145
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
2
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
32 Check if right triangle possible from given area and hypotenuse 178
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
37 Check whether a given point lies on or inside the rectangle | Set 3 210
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
3
Contents
53 Count of acute, obtuse and right triangles with given sides 303
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
54 Count of different straight lines with total n points with m collinear 307
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
62 Divide cuboid into cubes such that sum of volumes is maximum 354
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
4
Contents
72 Find all sides of a right angled triangle from given hypotenuse and area
| Set 1 410
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
73 Find an Integer point on a line segment with given two ends 414
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
74 Find area of parallelogram if vectors of two adjacent sides are given 417
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
79 Find minimum radius such that atleast k point lie inside the circle 438
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
5
Contents
88 Find the other end point of a line with given one end and mid 489
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
6
Contents
108 Lexicographically Kth smallest way to reach given coordinate from origin597
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602
7
Contents
116 Maximum number of 2×2 squares that can be fit inside a right isosceles
triangle 646
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650
118 Maximum number of squares that can fit in a right angle isosceles
triangle 654
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
126 Minimum height of a triangle with given base and area 690
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
130 Minimum number of square tiles required to fill the rectangular floor 703
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 710
8
Contents
138 Number of Triangles that can be formed given a set of lines in Euclidean
Plane 745
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749
140 Number of jump required of given length to reach a point of form (d,
0) from origin in 2D plane 758
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764
143 Number of possible pairs of Hypotenuse and Area to form right angled
triangle 781
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787
9
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811
148 Number of triangles in a plane if no more than two points are collinear818
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823
159 Probability that the pieces of a broken stick form a n sided polygon 875
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 876
10
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896
167 Program for Volume and Surface area of Frustum of Cone 911
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919
11
Contents
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993
181 Program to check if tank will overflow, underflow or filled in given time994
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 999
182 Program to check if the points are parallel to X axis or Y axis 1000
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1004
184 Program to check if water tank overflows when n solid balls are dipped
in the water tank 1012
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1019
186 Program to check whether 4 points in a 3-D plane are Coplanar 1034
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1037
188 Program to find third side of triangle using law of cosines 1043
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1049
12
Contents
208 Represent a given set of points by the best possible straight line 1156
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1163
210 Section formula (Point that divides a line in given ratio) 1167
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1172
211 Shortest distance between a Line and a Point in a 3-D plane 1173
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1178
13
Contents
221 Ways to choose three points with distance between the most distant
points <= L 1233
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1239
14
Chapter 1
15
Chapter 1. Angle between two Planes in 3D
16
Chapter 1. Angle between two Planes in 3D
Examples:
Input: a1 = 1, b1 = 1, c1 = 2, d1 = 1, a2 = 2, b2 = -1, c2 = 1, d2 = -4
Output: Angle is is 60.0 degree
Input: a1 = 2, b1 = 2, c1 = -3, d1 = -5, a2 = 3, b2 = -3, c2 = 5, d2 = -6
Output: Angle is 123.696598882 degree
P1 : a1 * x + b1 * y + c1 * z + d1 = 0 and,
P2 : a2 * x + b2 * y + c2 * z + d2 = 0,
where a1, b1, c1, and a2, b2, c2 are direction ratios of normal to the plane P1 and P2.
The angle between two planes is equal to the angle determined by the normal vectors of the
planes.
Angle between these planes is given by using the following formula:-
Cos A =
Using inverse property, we get:
A=
Below is the implementation of the above formulae:
// C program to find
// the Angle between
// two Planes in 3 D.
#include<stdio.h>
#include<math.h>
// Function to find Angle
void distance(float a1, float b1,
float c1, float a2,
float b2, float c2)
{
float d = (a1 * a2 + b1 *
b2 + c1 * c2);
float e1 = sqrt(a1 * a1 + b1 *
b1 + c1 * c1);
float e2 = sqrt(a2 * a2 + b2 *
b2 + c2 * c2);
17
Chapter 1. Angle between two Planes in 3D
Java
18
Chapter 1. Angle between two Planes in 3D
Python
19
Chapter 1. Angle between two Planes in 3D
b2 = -1
c2 = 1
d2 = -4
distance(a1, b1, c1, a2, b2, c2)
C#
// C# program to find
// the Angle between
// two Planes in 3 D.
using System;
class GFG
{
// Function to find Angle
static void distance(float a1, float b1,
float c1, float a2,
float b2, float c2)
{
float d = (a1 * a2 + b1 *
b2 + c1 * c2);
float e1 = (float)Math.Sqrt(a1 * a1 + b1 *
b1 + c1 * c1);
float e2 = (float)Math.Sqrt(a2 * a2 + b2 *
b2 + c2 * c2);
d = d / (e1 * e2);
float pi = (float)3.14159;
float A = (180 / pi) * (float)(Math.Acos(d));
Console.Write(“Angle is “+ A +” degree”);
}
// Driver code
public static void Main()
{
float a1 = 1;
float b1 = 1;
float c1 = 2;
float a2 = 2;
float b2 = -1;
float c2 = 1;
distance(a1, b1, c1,
a2, b2, c2);
}
}
// This code is contributed
// by ChitraNayal
PHP
20
Chapter 1. Angle between two Planes in 3D
<?php
// PHP program to find the Angle
// between two Planes in 3 D.
// Function to find Angle
function distance($a1, $b1,
$c1, $a2,
$b2, $c2)
{
$d = ($a1 * $a2 + $b1 *
$b2 + $c1 * $c2);
$e1 = sqrt($a1 * $a1 + $b1 *
$b1 + $c1 * $c1);
$e2 = sqrt($a2 * $a2 + $b2 *
$b2 + $c2 * $c2);
$d = $d / ($e1 * $e2);
$pi = 3.14159;
$A = (180 / $pi) * (acos($d));
echo sprintf("Angle is %.2f degree", $A);
}
// Driver Code
$a1 = 1;
$b1 = 1;
$c1 = 2;
$d1 = 1;
$a2 = 2;
$b2 = -1;
$c2 = 1;
$d2 = -4;
distance($a1, $b1, $c1,
$a2, $b2, $c2);
// This code is contributed
// by Amber_Saxena.
?>
Output:
Source
https://www.geeksforgeeks.org/angle-between-two-planes-in-3d/
21
Chapter 2
Angular Sweep (Maximum points that can be enclosed in a circle of given radius) - Geeks-
forGeeks
Given ‘n’ points on 2-D plane, find the maximum number of points that can be enclosed by
a fixed-radius circle of radius ‘R’.
Note: The point is considered to be inside the circle even when it lies on the circumference.
Examples:
Input : R = 1
points[] = {(6.47634, 7.69628), (5.16828 4.79915),
(6.69533 6.20378)}
Output : 2
The maximum number of points are 2
Input : R = 1
points[] = {(6.65128, 5.47490), (6.42743, 6.26189)
(6.35864, 4.61611), (6.59020 4.54228), (4.43967 5.70059)
(4.38226, 5.70536), (5.50755 6.18163), (7.41971 6.13668)
(6.71936, 3.04496), (5.61832, 4.23857), (5.99424, 4.29328)
(5.60961, 4.32998), (6.82242, 5.79683), (5.44693, 3.82724)
(6.70906, 3.65736), (7.89087, 5.68000), (6.23300, 4.59530)
(5.92401, 4.92329), (6.24168, 3.81389), (6.22671, 3.62210)}
Output : 11
The maximum number of points are 11
22
Chapter 2. Angular Sweep (Maximum points that can be enclosed in a circle of given
radius)
Naive Algorithm
1. For an arbitrary pair of points in the given set (say A and B), construct the circles
with radius ‘R’ that touches both the points. There are maximum 2 such possible
circles. As we can see here maximum possible circles is for CASE 1 i.e. 2.
2. For each of the constructed circle, check for each point in the set if it lies inside the
circle or not.
3. The circle with maximum number of points enclosed is returned.
Time Complexity: There are n C2 pair of points corresponding to which we can have 2n C2
circles at maximum. For each circle, (n-2) points have to be checked. This makes the naive
algorithm O(n3 ).
23
Chapter 2. Angular Sweep (Maximum points that can be enclosed in a circle of given
radius)
In the given diagram, C1 is the circle with Θ = 0 and C2 is the circle constructed when we
rotate the circle at a general value of Θ.
After this, the problem reduces to, how to maintain the value of count.
For any given point except P (say Q), we can easily calculate the value of Θ for which it
enters the circle (Let it be �) and the value of Θ for which it exits the circle (Let it be �).
We have angles A and B defined as under,
where, x and y represent the coordinates of a point and ‘d’ is the distance between P and
Q.
Now, from the diagrams we can see that,
� = A-B
� = A+B
(Note: All angles are w.r.t. to X-Axis. Thus, it becomes ‘A-B’ and not ‘B-A’).
When Q enters the circle
24
Chapter 2. Angular Sweep (Maximum points that can be enclosed in a circle of given
radius)
We can calculate angles A and B for all points excluding P. Once these angles are found, we
sort them and then traverse them in increasing order. Now we maintain a counter which
tells us how many points are inside the circle at a particular moment.
Count will change only when a point enters the circle or exits it. In case we find an entry
angle we increase the counter by 1 and in case we find an exit angle we decrease the counter
by 1. The check that the angle is entry or exit can be easily realised using a flag.
Proceeding like this, the counter always gives us a valid value for number of points inside
the circle in a particular state.
Important Note: The points which have ‘d’>2R do not have to be considered because
the will never enter or exit the circle.
The angular sweep algorithm can be described as:
1. Calculate the distance between every pair of n C2 points and store them.
2. For an arbitrary point (say P), get the maximum number of points that can lie inside
the circle rotated about P using the getPointsInside() function.
25
Chapter 2. Angular Sweep (Maximum points that can be enclosed in a circle of given
radius)
26
Chapter 2. Angular Sweep (Maximum points that can be enclosed in a circle of given
radius)
// count maintains the number of points inside
// the circle at certain value of theta
// res maintains the maximum of all count
int count = 1, res = 1;
vector<pair<double, bool> >::iterator it;
for (it=angles.begin(); it!=angles.end(); ++it)
{
// entry angle
if ((*it).second)
count++;
// exit angle
else
count--;
if (count > res)
res = count;
}
return res;
}
// Returns count of maximum points that can lie
// in a circle of radius r.
int maxPoints(Point arr[], int n, int r)
{
// dis array stores the distance between every
// pair of points
for (int i=0; i<n-1; i++)
for (int j=i+1; j<n; j++)
// abs gives the magnitude of the complex
// number and hence the distance between
// i and j
dis[i][j] = dis[j][i] = abs(arr[i]-arr[j]);
// This loop picks a point p
int ans = 0;
for (int i=0; i<n; i++)
// maximum number of points for point arr[i]
ans = max(ans, getPointsInside(i, r, n));
return ans;
}
// Driver code
27
Chapter 2. Angular Sweep (Maximum points that can be enclosed in a circle of given
radius)
int main()
{
Point arr[] = {Point(6.47634, 7.69628),
Point(5.16828, 4.79915),
Point(6.69533, 6.20378)};
int r = 1;
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum number of points are: "
<< maxPoints(arr, n, r);
return 0;
}
Output :
Time Complexity: There are n points for which we call the function getPointsInside().
This function works on ‘n-1’ points for which we get 2*(n-1) size of the vector ‘angles’ (one
entry angle and one exit angle). Now this ‘angles’ vector is sorted and traversed which gives
complexity of the getPointsInside() function equal to O(nlogn). This makes the Angular
Sweep Algorithm O(n2 log n).
Related Resources: Using the complex class available in stl for implementing solutions
to geometry problems.
http://codeforces.com/blog/entry/22175
Source
https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/
28
Chapter 3
Given an angle and the diameter of a circle, we can calculate the length of the arc using the
formula:
Examples :
29
Chapter 3. Arc length from given Angle
Input :
Diameter = 25
Angle = 45
Explanation : ((22/7) * 25) * (45/360)
Output : 9.821 (rounded)
Input :
Diameter = 80
Angle = 60
Explanation : ((22/7) * 80) * (60/360)
Output : 41.905 (rounded)
Note: If angle is greater than or equal to 360 degree, then the arc length cannot be
calculated, since no angle is possible.
C++
30
Chapter 3. Arc length from given Angle
Java
Python3
31
Chapter 3. Arc length from given Angle
# length of an arc
import math
# functuion to calculate arc length
def arcLength(diameter, angle ):
if angle >= 360:
print("Angle cannot be formed")
return 0
else:
arc = (3.142857142857143 * diameter) * (angle / 360.0)
return arc
# Driver Code
diameter = 25.0
angle = 45.0
arc_len = arcLength(diameter, angle)
print(arc_len)
# This code is contributed by "Sharad_Bhardwaj".
C#
32
Chapter 3. Arc length from given Angle
double diameter = 25.0;
double angle = 45.0;
double arc_len = arcLength(diameter, angle);
Console.WriteLine(arc_len);
}
}
// This code is contributed by Anant Agarwal.
PHP
<?php
// PHP program to calculate
// length of an arc
// functuion to calculate
// arc length
function arcLength($diameter,
$angle)
{
$pi = 22.0 / 7.0;
$arc;
if ($angle >= 360)
{
echo "Angle cannot",
" be formed";
return 0;
}
else
{
$arc = ($pi * $diameter) *
($angle / 360.0);
return $arc;
}
}
// Driver Code
$diameter = 25.0;
$angle = 45.0;
$arc_len = arcLength($diameter, $angle);
echo ($arc_len);
// This code is contributed by ajit
?>
33
Chapter 3. Arc length from given Angle
Output:
9.821428571428571
Improved By : jit_t
Source
https://www.geeksforgeeks.org/arc-length-angle/
34
Chapter 4
35
Chapter 4. Area of a Circular Sector
The area of the sector is similar to the calculation of the area of the circle, just multiply
the area of the circle with the angle of the sector.
Examples:
Input:
radius = 9
angle = 60
Explanation:
Sector = ( pi * 9*9 ) * ( 60 / 360 )
Output: 42.42857142857142
Input:
radius = 20
angle = 145
Explanation:
Sector = ( pi * 20*20 ) * ( 145 / 360 )
Output: 506.3492063492063
C++
36
Chapter 4. Area of a Circular Sector
cout<<sector;
}
}
// Driver code
int main()
{
double radius = 9;
double angle = 60;
SectorArea(radius, angle);
return 0;
}
// This code is contributed by Anant Agarwal.
Java
Python3
37
Chapter 4. Area of a Circular Sector
def SectorArea(radius, angle):
pi = 22 / 7
# Constraint or Limit
if angle >= 360:
print("Angle not possible")
return
# Calculating area of the sector
else:
sector = (pi * radius ** 2) * (angle / 360)
print(sector)
return
# Driver code
radius = 9
angle = 60
SectorArea(radius, angle)
C#
38
Chapter 4. Area of a Circular Sector
SectorArea(radius, angle);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find Area of a Sector
function SectorArea( $radius, $angle)
{
if($angle >= 360)
echo("Angle not possible");
// Calculating area of the sector
else
{
$sector = ((22 * $radius * $radius)
/ 7) * ($angle / 360);
echo($sector);
}
}
// Driver code
$radius = 9;
$angle = 60;
SectorArea($radius, $angle);
// This code is contributed by vt_m.
?>
Output:
42.42857142857142
Source
https://www.geeksforgeeks.org/area-of-a-sector/
39
Chapter 5
Input : a = 6
Output : Area of a circumscribed circle is : 56.55
Input : a = 4
Output : Area of a circumscribed circle is : 25.13
All four sides of a square are of equal length and all four angles are 90 degree. The circle is
circumscribed on a given square shown by a shaded region in the below diagram.
40
Chapter 5. Area of a Circumscribed Circle of a Square
• The center of the circumcircle is the point where the two diagonals of a square meet.
• Circumscribed circle of a square is made through the four vertices of a square.
• The radius of a circumcircle of a square is equal to the radius of a square.
C++
Java
41
Chapter 5. Area of a Circumscribed Circle of a Square
float PI = 3.14159265f;
return (a * a * (PI / 2));
}
// Driver Function
public static void main(String arg[])
{
float a = 6;
System.out.print("Area of an circumscribed"
+ "circle is :");
System.out.println(areacircumscribed(a));
}
}
// The code is contributed by Anant Agarwal.
Python3
C#
42
Chapter 5. Area of a Circumscribed Circle of a Square
// Driver code
public static void Main()
{
float a = 6;
Console.Write(" Area of an circumscribed"
+ " circle is : {0}",
Math.Round(areacircumscribed(a), 2));
}
}
// This code is contributed by
// Smitha Dinesh Semwal
PHP
<?php
// PHP Program to find the
// area of a circumscribed
// circle
$PI = 3.14159265;
// function returns the area
function areacircumscribed($a)
{
global $PI;
return ($a * $a * ($PI / 2));
}
// Driver code
$a = 6;
echo " Area of an circumscribed circle is : ",
areacircumscribed($a);
// The code is contributed by anuj_67.
?>
Output :
43
Chapter 5. Area of a Circumscribed Circle of a Square
Source
https://www.geeksforgeeks.org/area-circumscribed-circle-square/
44
Chapter 6
Area of a Hexagon
Examples :
Input: 4
Output: 41.5692
Input: 6
Output: 93.5307
Number of vertices: 6
Number of edges: 6
Internal angle: 120°
Area = (3 √3(side)2 ) / 2
45
Chapter 6. Area of a Hexagon
C++
Java
class GFG
{
// Create a function for calculating
// the area of the hexagon.
public static double hexagonArea(double s)
{
return ((3 * Math.sqrt(3) *
(s * s)) / 2);
}
// Driver Code
public static void main(String[] args)
{
// Length of a side
double s = 4;
System.out.print("Area: " +
hexagonArea(s) );
}
}
46
Chapter 6. Area of a Hexagon
C#
// C# program to find
// area of a Hexagon
using System;
class GFG
{
// Create a function for calculating
// the area of the hexagon.
public static double hexagonArea(double s)
{
return ((3 * Math.Sqrt(3) *
(s * s)) / 2);
}
// Driver Code
public static void Main()
{
// Length of a side
double s = 4;
Console.WriteLine("Area: " +
hexagonArea(s) );
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find
// area of a Hexagon
// function for calculating
// area of the hexagon.
function hexagonArea( $s)
{
return ((3 * sqrt(3) *
($s * $s)) / 2);
}
// Driver Code
// Length of a side
47
Chapter 6. Area of a Hexagon
$s = 4;
echo("Area : ");
echo(hexagonArea($s));
// This code is contributed by vt_m.
?>
Output :
Area: 41.5692
Source
https://www.geeksforgeeks.org/area-of-a-hexagon/
48
Chapter 7
Area
CPP
49
Chapter 7. Area of a polygon with given n ordered vertices
#include <bits/stdc++.h>
using namespace std;
// (X[i], Y[i]) are coordinates of i'th point.
double polygonArea(double X[], double Y[], int n)
{
// Initialze area
double area = 0.0;
// Calculate value of shoelace formula
int j = n - 1;
for (int i = 0; i < n; i++)
{
area += (X[j] + X[i]) * (Y[j] - Y[i]);
j = i; // j is previous vertex to i
}
// Return absolute value
return abs(area / 2.0);
}
// Driver program to test above function
int main()
{
double X[] = {0, 2, 4};
double Y[] = {1, 3, 7};
int n = sizeof(X)/sizeof(X[0]);
cout << polygonArea(X, Y, n);
}
Java
50
Chapter 7. Area of a polygon with given n ordered vertices
int j = n - 1;
for (int i = 0; i < n; i++)
{
area += (X[j] + X[i]) * (Y[j] - Y[i]);
// j is previous vertex to i
j = i;
}
// Return absolute value
return Math.abs(area / 2.0);
}
// Driver program
public static void main (String[] args)
{
double X[] = {0, 2, 4};
double Y[] = {1, 3, 7};
int n = 3;
System.out.println(polygonArea(X, Y, n));
}
}
// This code is contributed by Sunnnysingh
Python3
51
Chapter 7. Area of a polygon with given n ordered vertices
C#
52
Chapter 7. Area of a polygon with given n ordered vertices
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to evaluate area of
// a polygon using shoelace formula
// (X[i], Y[i]) are
// coordinates of i'th point.
function polygonArea($X, $Y, $n)
{
// Initialze area
$area = 0.0;
// Calculate value of
// shoelace formula
$j = $n - 1;
for ($i = 0; $i < $n; $i++)
{
$area += ($X[$j] + $X[$i]) *
($Y[$j] - $Y[$i]);
// j is previous vertex to i
$j = $i;
}
// Return absolute value
return abs($area / 2.0);
}
// Driver Code
$X = array(0, 2, 4);
$Y = array(1, 3, 7);
$n = sizeof($X);
echo polygonArea($X, $Y, $n);
// This code is contributed by ajit
?>
Output :
53
Chapter 7. Area of a polygon with given n ordered vertices
54
Chapter 7. Area of a polygon with given n ordered vertices
This article is contributed by Utkarsh Trivedi. Please write comments if you find anything
incorrect, or you want to share more information about the topic discussed above
Improved By : jit_t
Source
https://www.geeksforgeeks.org/area-of-a-polygon-with-given-n-ordered-vertices/
55
Chapter 8
Input : r = 3
Output :Area of square = 18
Input :r = 6
Output :Area of square = 72
All four sides of a square are of equal length and all four angles are 90 degree. The circle is
circumscribed on a given square shown by a shaded region in the below diagram.
• The center of the circumcircle is the point where the two diagonals of a square meet.
56
Chapter 8. Area of square Circumscribed by Circle
CPP
57
Chapter 8. Area of square Circumscribed by Circle
return 0;
}
Java
Python3
# Python program to
# find Area of
# square Circumscribed
# by Circle
# Function to find
# area of square
def find_Area(r):
return (2 * r * r)
# driver code
# Radius of a circle
r = 3
58
Chapter 8. Area of square Circumscribed by Circle
# Call Function to find
# an area of square
print(" Area of square = ", find_Area(r))
# This code is contributed
# by Anant Agarwal.
C#
PHP
<?php
// PHP program to find Area of
// square Circumscribed by Circle
// Function to find area of square
function find_Area( $r)
{
return (2 * $r * $r);
59
Chapter 8. Area of square Circumscribed by Circle
}
// Driver code
// Radius of a circle
$r = 3;
// Call Function to find
// an area of square
echo ("Area of square = ");
echo(find_Area($r));
// This code is contributed by vt_m.
?>
Output:
Area of square = 18
Source
https://www.geeksforgeeks.org/area-square-circumscribed-circle/
60
Chapter 9
61
Chapter 9. Bresenham’s Algorithm for 3-D Line Drawing
linearly by 1 along the driving axis and the slope-error variable is used to determine the
change in the co-ordinate values of the other axis.
In case of a 2-D line we use one slope-error variable but in case of a 3-D line we need two
( ) of them for each of the non-driving axes. If current point is (x, y, z) and
the driving axis is the positive X-axis, then the next point could be
• (x+1, y, z)
• (x+1, y+1, z)
• (x+1, y, z+1)
• (x+1, y+1, z+1)
The value of slope-error variables are determined according to the following equations:-
The initial value of slope-error variables are given by the following equations:-
Here denote the difference in co-ordinates of the two end points along
the X, Y, Z axes.
Algorithm:-
62
Chapter 9. Bresenham’s Algorithm for 3-D Line Drawing
2. Plot
3. Calculate constants and determine the driving axis by comparing
• If AND , then
plot and
set
• Else If AND , then
plot and
set
• Else If , then
plot and
set
• Else then
plot and
set >
Python3
63
Chapter 9. Bresenham’s Algorithm for 3-D Line Drawing
64
Chapter 9. Bresenham’s Algorithm for 3-D Line Drawing
p2 += 2 * dz
ListOfPoints.append((x1, y1, z1))
# Driving axis is Z-axis"
else:
p1 = 2 * dy - dz
p2 = 2 * dx - dz
while (z1 != z2):
z1 += zs
if (p1 >= 0):
y1 += ys
p1 -= 2 * dz
if (p2 >= 0):
x1 += xs
p2 -= 2 * dz
p1 += 2 * dy
p2 += 2 * dx
ListOfPoints.append((x1, y1, z1))
return ListOfPoints
def main():
(x1, y1, z1) = (-1, 1, 1)
(x2, y2, z2) = (5, 3, -1)
ListOfPoints = Bresenham3D(x1, y1, z1, x2, y2, z2)
print(ListOfPoints)
main()
Output:
[(-1, 1, 1), (0, 1, 1), (1, 2, 0), (2, 2, 0), (3, 2, 0), (4, 3, -1), (5, 3, -1)]
Source
https://www.geeksforgeeks.org/bresenhams-algorithm-for-3-d-line-drawing/
65
Chapter 10
66
Chapter 10. Calculate Volume and Surface area Of Sphere
Examples :
C++
67
Chapter 10. Calculate Volume and Surface area Of Sphere
{
float sur_ar;
sur_ar = 4 * pi * r * r;
return sur_ar;
}
// Driver Function
int main()
{
float radius = 12;
float vol, sur_area;
// Function Call
vol = volume(radius);
sur_area = surface_area(radius);
// Printing Value Of Volume And Surface Area
cout << "Volume Of Sphere :" << vol << endl;
cout << "Surface Area Of Sphere :" << sur_area << endl;
return 0;
}
Java
68
Chapter 10. Calculate Volume and Surface area Of Sphere
{
float radius = 12;
float vol, sur_area;
// Function Call
vol = volume(radius);
sur_area = surface_area(radius);
// Printing Value Of Volume And Surface Area
System.out.println("Volume Of Sphere :" + vol);
System.out.println("Surface Area Of Sphere :" + sur_area);
}
}
// This code is contributed by Anant Agarwal.
Python3
C#
69
Chapter 10. Calculate Volume and Surface area Of Sphere
PHP
<?php
// CPP program to calculate Volume
// and Surface area of Sphere
70
Chapter 10. Calculate Volume and Surface area Of Sphere
// Function To Calculate
// Volume Of Sphere
function volume( $r)
{
$pi = 3.14159;
$vol = (4 / 3) * $pi * $r * $r * $r;
return $vol;
}
// Function To Calculate
// Surface Area of Sphere
function surface_area( $r)
{
$pi = 3.14159;
$sur_ar = 4 * $pi * $r * $r;
return $sur_ar;
}
// Driver Code
$radius = 12;
$vol; $sur_area;
// Function Call
$vol = volume($radius);
$sur_area = surface_area($radius);
// Printing Value Of
// Volume And Surface Area
echo ("Volume Of Sphere : " );
echo($vol);
echo( " \nSurface Area Of Sphere :");
echo( $sur_area);
// This code is contributed by vt_m.
?>
Output :
Improved By : vt_m
71
Chapter 10. Calculate Volume and Surface area Of Sphere
Source
https://www.geeksforgeeks.org/calculate-volume-surface-area-sphere/
72
Chapter 11
Calculate Volume of
Dodecahedron
Input : side = 4
Output : 490.44
Input : side = 9
Output : 5586.41
C++
73
Chapter 11. Calculate Volume of Dodecahedron
{
return (((15 + (7 * (sqrt(5)))) / 4)
* (pow(side, 3))) ;
}
// Driver Function
int main()
{
int side = 4;
cout << "Volume of dodecahedron = "
<< vol_of_dodecahedron(side);
}
Java
Python3
74
Chapter 11. Calculate Volume of Dodecahedron
def vol_of_dodecahedron(side) :
return (((15 + (7 * (math.sqrt(5)))) / 4)
* (math.pow(side, 3)))
# Driver Function
side = 4
print("Volume of dodecahedron =",
round(vol_of_dodecahedron(side), 2))
# This code is contributed by Smitha Dinesh Semwal
C#
// C# program to calculate
// Volume of dodecahedron
using System;
public class GFG
{
// utility Function
static float vol_of_dodecahedron(int side)
{
return (float)(((15 + (7 * (Math.Sqrt(5)))) / 4)
* (Math.Pow(side, 3))) ;
}
// Driver Function
static public void Main ()
{
int side = 4;
Console.WriteLine("Volume of dodecahedron = "
+ vol_of_dodecahedron(side));
}
}
/* This code is contributed by vt_m.*/
PHP
<?php
// PHP program to calculate
// Volume of dodecahedron
75
Chapter 11. Calculate Volume of Dodecahedron
// utility Function
function vol_of_dodecahedron($side)
{
return (((15 + (7 * (sqrt(5)))) / 4)
* (pow($side, 3))) ;
}
// Driver Function
$side = 4;
echo ("Volume of dodecahedron = ");
echo(vol_of_dodecahedron($side));
// This code is contributed by vt_m.
?>
Output :
Improved By : vt_m
Source
https://www.geeksforgeeks.org/calculate-volume-dodecahedron/
76
Chapter 12
Cone :
Cone is a three dimensional geometric shape. It consists of a base having the shape of a
circle and a curved side (the lateral surface) ending up in a tip called the apex or vertex.
Volume of a cone :
The volume of a cone is given by the formula –
volume = 1/3(pi * r * r * h)
where r is the radius of the circular base, and h is the height (the perpendicular distance
from the base to the vertex).
Surface area of a cone :
The surface area of a cone is given by the formula –
77
Chapter 12. Calculate volume and surface area of a cone
area = pi * r * s + pi * r^2
Where r is the radius of the circular base, and s is the slant height of the cone.
Examples :
Input :
radius = 5
slant_height = 13
height = 12
Output :
Volume Of Cone = 314.159
Surface Area Of Cone = 282.743
Input :
radius = 6
slant_height = 10
height = 8
Output :
Volume Of Cone = 301.593
Surface Area Of Cone = 301.593
C++
78
Chapter 12. Calculate volume and surface area of a cone
int main()
{
float radius = 5;
float slant_height = 13;
float height = 12;
float vol, sur_area;
// Printing value of volume
// and surface area
cout << "Volume Of Cone : "
<< volume(radius, height) << endl;
cout << "Surface Area Of Cone : "
<< surface_area(radius, slant_height);
return 0;
}
Java
79
Chapter 12. Calculate volume and surface area of a cone
// Printing value of volume
// and surface area
System.out.print("Volume Of Cone : ");
System.out.println(volume(radius, height));
System.out.print("Surface Area Of Cone : ");
System.out.println(surface_area(radius,
slant_height));
}
}
// This code is contributed by "akanshgupta"
Python
C#
// C# program to calculate
// Volume and Surface area of cone
using System;
class GFG
{
80
Chapter 12. Calculate volume and surface area of a cone
PHP
<?php
// PHP program to calculate Volume
// and Surface area of Cone
81
Chapter 12. Calculate volume and surface area of a cone
Output :
Improved By : vt_m
Source
https://www.geeksforgeeks.org/calculate-volume-surface-area-cone/
82
Chapter 13
Input : 3
Output : 37
Input : 7
Output :253
83
Chapter 13. Centered Dodecagonal Number
C++
Java
84
Chapter 13. Centered Dodecagonal Number
return 6 * n * (n - 1) + 1;
}
// Driver Code
public static void main (String[] args)
{
long n = 2;
System.out.println(centeredDodecagonal(n));
n = 9;
System.out.println(centeredDodecagonal(n));
}
}
// This code is contributed by anuj_67.
Output :
13
433
References
http://oeis.org/A003154
Improved By : vt_m
Source
https://www.geeksforgeeks.org/centered-dodecagonal-number/
85
Chapter 14
Centered Octadecagonal
Number
Examples :
Input : 2
Output : 19
Input : 6
Output : 271
86
Chapter 14. Centered Octadecagonal Number
Java
87
Chapter 14. Centered Octadecagonal Number
Python3
88
Chapter 14. Centered Octadecagonal Number
center_octadecagon_num(n))
n = 13
print(n,"th centered octadecagonal " +
"number : ",
center_octadecagon_num(n))
# This code is contributed
# by akt_mit
C#
PHP
89
Chapter 14. Centered Octadecagonal Number
<?php
// PHP Program to find the
// nth centered octadecagonal
// number
// centered octadecagon function
function center_octadecagon_num($n)
{
// Formula to calculate nth
// centered octadecagonal number
return (9 * $n * $n -
9 * $n + 1);
}
// Driver Code
$n = 3;
echo $n , "th centered octadecagonal " .
"number : ",
center_octadecagon_num($n);
echo "\n";
$n = 13;
echo $n , "th centered octadecagonal " .
"number : ",
center_octadecagon_num($n);
// This code is contributed by m_kit
?>
Output :
Improved By : jit_t
Source
https://www.geeksforgeeks.org/centered-octadecagonal-number/
90
Chapter 15
Examples :
Input : 2
Output : 9
Input : 5
Output : 81
91
Chapter 15. Centered Octagonal Number
C++
Java
92
Chapter 15. Centered Octagonal Number
Python3
93
Chapter 15. Centered Octagonal Number
cen_octagonalnum(n))
n = 11
print(n,"th Centered" ,
"octagonal number: ",
cen_octagonalnum(n))
# This code is contributed
# by akt_mit
C#
PHP
<?php
94
Chapter 15. Centered Octagonal Number
Output
Source
https://www.geeksforgeeks.org/centered-octagonal-number/
95
Chapter 16
Centered Pentadecagonal
Number
Examples :
Input : 2
Output : 16
Input : 8
Output : 421
96
Chapter 16. Centered Pentadecagonal Number
Java
97
Chapter 16. Centered Pentadecagonal Number
Python3
98
Chapter 16. Centered Pentadecagonal Number
C#
// C# Program to find
// nth centered
// pentadecagonal number
using System;
class GFG
{
// centered
// pentadecagonal function
static long center_pentadecagonal_num(long n)
{
// Formula to calculate
// nth centered
// pentadecagonal number
return (15 * n * n -
15 * n + 2) / 2;
}
// Driver Code
static public void Main ()
{
long n = 3;
Console.Write(n + "th number : ");
Console.WriteLine(
center_pentadecagonal_num(n));
n = 10;
Console.Write( n + "th number : ");
Console.WriteLine(
center_pentadecagonal_num(n));
}
}
// This code is contributed by ajit.
PHP
<?php
// PHP Program to find
// nth centered
// pentadecagonal number
99
Chapter 16. Centered Pentadecagonal Number
// centered pentadecagonal function
function center_pentadecagonal_num($n)
{
// Formula to calculate nth
// centered pentadecagonal number
return (15 * $n * $n -
15 * $n + 2) / 2;
}
// Driver Code
$n = 3;
echo $n , "th number : ",
center_pentadecagonal_num($n);
echo "\n";
$n = 10;
echo $n , "th number : ",
center_pentadecagonal_num($n);
// This code is contributed by m_kit
?>
Output :
3th number : 46
10th number : 676
Improved By : jit_t
Source
https://www.geeksforgeeks.org/centered-pentadecagonal-number/
100
Chapter 17
Input : n = 1
Output : 9
Input : n = 7
Output : 855
101
Chapter 17. Centered cube number
// Function to find
// Centered cube number
int centered_cube(int n)
{
// Formula to calculate nth
// Centered cube number &
// return it into main function.
return (2 * n + 1) * ( n * n + n + 1);
}
// Driver Code
int main()
{
int n = 3;
cout << n << "th Centered cube number: ";
cout << centered_cube(n);
cout << endl;
n = 10;
cout << n << "th Centered cube number: ";
cout << centered_cube(n);
return 0;
}
Java
102
Chapter 17. Centered cube number
Python3
C#
103
Chapter 17. Centered cube number
using System;
class GFG
{
// Function to find
// Centered cube number
static int centered_cube(int n)
{
// Formula to calculate
// nth Centered cube
// number & return it
// into main function.
return (2 * n + 1) *
(n * n + n + 1);
}
// Driver code
static public void Main ()
{
int n = 3;
Console.Write(n + "th Centered" +
" cube number: ");
Console.WriteLine (centered_cube(n));
n = 10;
Console.Write( n + "th Centered" +
" cube number: ");
Console.WriteLine(centered_cube(n));
}
}
// This code is contributed by aj_36
PHP
<?php
// Program to find nth
// Centered cube number
// Function to find
// Centered cube number
function centered_cube($n)
{
// Formula to calculate nth
// Centered cube number &
// return it into main function.
return (2 * $n + 1) *
104
Chapter 17. Centered cube number
($n * $n + $n + 1);
}
// Driver Code
$n = 3;
echo $n , "th Centered cube number: ";
echo centered_cube($n);
echo "\n";
$n = 10;
echo $n , "th Centered cube number: ";
echo centered_cube($n);
// This code is contributed by m_kit
?>
Output :
Improved By : jit_t
Source
https://www.geeksforgeeks.org/centered-cube-number/
105
Chapter 18
Input : 3
Output : 31
106
Chapter 18. Centered decagonal number
Input : 6
Output : 151
Java
107
Chapter 18. Centered decagonal number
Python 3
108
Chapter 18. Centered decagonal number
5 * n + 1)
# Driver Code
if __name__ == '__main__' :
n = 5
print(n,"th centered decagonal " +
"number : ",
centereddecagonalnum(n))
n = 9
print(n,"th centered decagonal " +
"number : ",
centereddecagonalnum(n))
# This code is contributed by m_kit
C#
109
Chapter 18. Centered decagonal number
}
}
// This code is contributed by aj_36
PHP
<?php
// Program to find nth
// centered decagonal number
// Centered decagonal
// number function
function centereddecagonalnum($n)
{
// Formula to calculate
// nth centered decagonal
// number & return it
// into main function.
return (5 * $n * $n +
5 * $n + 1);
}
// Driver Code
$n = 5;
echo $n , "th centered decagonal",
"number: ";
echo centereddecagonalnum($n);
echo "\n";
$n = 9;
echo $n , "th centered decagonal",
"number: ";
echo centereddecagonalnum($n);
// This code is contributed by ajit
?>
Output
Improved By : jit_t
110
Chapter 18. Centered decagonal number
Source
https://www.geeksforgeeks.org/centered-decagonal-number/
111
Chapter 19
Input : 5
Output : 1661
Input :1
Output :33
Mathematical formula for the nth Centered dodecahedral number is given by:
112
Chapter 19. Centered dodecahedral number
// Function to find
// centered dodecahedral number
int CenteredDodecahedral_num(long int n)
{
// Formula to calculate nth
// centered dodecahedral number
// and return it into main function.
return (2 * n + 1) * (5 * n * n + 5 * n + 1);
}
// Driver Code
int main()
{
long int n = 3;
// print result
cout << n << "th Centered Dodecahedral number : ";
cout << CenteredDodecahedral_num(n) << endl;
n = 10;
// print result
cout << n << "th Centered Dodecahedral number : ";
cout << CenteredDodecahedral_num(n);
return 0;
}
Java
113
Chapter 19. Centered dodecahedral number
{
int n = 3;
// print result
System.out.print( n + "th Centered "
+ "Dodecahedral number : ");
System.out.println (
CenteredDodecahedral_num(n));
n = 10;
// print result
System.out.print( n + "th Centered "
+ "Dodecahedral number : ");
System.out.println(
CenteredDodecahedral_num(n));
}
}
// This code is contributed by m_kit.
Python3
C#
114
Chapter 19. Centered dodecahedral number
// C# Program to find
// nth centered
// dodecahedral number
using System;
class GFG
{
// Function to find
// nth centered
// dodecahedral number
static int CenteredDodecahedral_num(int n)
{
// Formula to calculate
// nth centered dodecahedral
// number and return it
// into main function.
return (2 * n + 1) *
(5 * n * n +
5 * n + 1);
}
// Driver Code
static public void Main ()
{
int n = 3;
// print result
Console.Write( n + "th Centered " +
"Dodecahedral number : ");
Console.WriteLine(
CenteredDodecahedral_num(n));
n = 10;
// print result
Console.Write( n + "th Centered " +
"Dodecahedral number : ");
Console.WriteLine(
CenteredDodecahedral_num(n));
}
}
// This code is contributed by ajit
PHP
115
Chapter 19. Centered dodecahedral number
<?php
// Program to find nth centered
// dodecahedral number
// Function to find
// centered dodecahedral number
function CenteredDodecahedral_num($n)
{
// Formula to calculate nth
// centered dodecahedral number
// and return it into main function.
return (2 * $n + 1) *
(5 * $n * $n +
5 * $n + 1);
}
// Driver Code
$n = 3;
// print result
echo $n, "th Centered Dodecahedral " .
"number : ";
echo CenteredDodecahedral_num($n),"\n";
$n = 10;
// print result
echo $n, "th Centered Dodecahedral " .
"number : ";
echo CenteredDodecahedral_num($n);
// This code is contributed by akt_mit
?>
Output :
References:
https://en.wikipedia.org/wiki/Centered_dodecahedral_number
Improved By : jit_t
Source
https://www.geeksforgeeks.org/centered-dodecahedral-number/
116
Chapter 20
Centered nonadecagonal
number
Input : 3
Output : 58
117
Chapter 20. Centered nonadecagonal number
Input : 13
Output :1483
Java
118
Chapter 20. Centered nonadecagonal number
class GFG {
// centered nonadecagonal
// function
static int center_nonadecagon_num(int n)
{
// Formula to calculate nth
// centered nonadecagonal number
return (19 * n * n - 19 * n + 2) / 2;
}
// Driver code
public static void main (String[] args)
{
int n = 2;
System.out.print ( n + "th centered "
+ "nonadecagonal number : ");
System.out.println (
center_nonadecagon_num(n));
n = 7;
System.out.print ( n + "th centered "
+ "nonadecagonal number : ");
System.out.println(
center_nonadecagon_num(n));
}
}
// This code is contributed by m_kit
Python3
119
Chapter 20. Centered nonadecagonal number
C#
// C# Program to find
// nth centered
// nonadecagonal number
using System;
class GFG
{
// centered nonadecagonal
// function
static int center_nonadecagon_num(int n)
{
// Formula to calculate nth
// centered nonadecagonal number
return (19 * n * n -
19 * n + 2) / 2;
}
// Driver code
static public void Main ()
{
int n = 2;
Console.Write ( n + "th centered " +
"nonadecagonal number : ");
Console.WriteLine(
center_nonadecagon_num(n));
n = 7;
Console.Write( n + "th centered " +
"nonadecagonal number : ");
Console.WriteLine(
center_nonadecagon_num(n));
}
}
120
Chapter 20. Centered nonadecagonal number
// This code is contributed by ajit
PHP
<?php
// PHP Program to find
// nth centered
// nonadecagonal number
// centered nonadecagonal
// function
function center_nonadecagon_num( $n )
{
// Formula to calculate nth
// centered nonadecagonal number
return (19 * $n * $n -
19 * $n + 2) / 2;
}
// Driver Code
$n = 2;
echo $n ,"th centered " +
"nonadecagonal number : ",
center_nonadecagon_num($n);
echo "\n";
$n = 7;
echo $n , "th centered " +
"nonadecagonal number : ",
center_nonadecagon_num($n);
// This code is contributed by ajit
?>
Output :
References:
http://oeis.org/A069132
Improved By : jit_t
Source
https://www.geeksforgeeks.org/centered-nonadecagonal-number/
121
Chapter 21
122
Chapter 21. Centered pentagonal number
Input : 3
Output : 16
Input : 9
Output : 181
Approach:
Centered pentagonal for n-th term is given by :
123
Chapter 21. Centered pentagonal number
C++
Java
124
Chapter 21. Centered pentagonal number
return (5 * n * n - 5 * n + 2) / 2;
}
// Driver Code
public static void main (String[] args)
{
int n = 7;
System.out.print(n + "th Centered " +
"pentagonal number: ");
System.out.println(centered_pentagonal_Num(n));
}
}
// This code is contributed by anuj_67.
Python3
C#
125
Chapter 21. Centered pentagonal number
// number function
static int centered_pentagonal_Num(int n)
{
// Formula to calculate
// nth Centered pentagonal
// number and return it
// into main function.
return (5 * n * n - 5 * n + 2) / 2;
}
// Driver Code
public static void Main ()
{
int n = 7;
Console.Write(n + "th Centered " +
"pentagonal number: ");
Console.WriteLine(centered_pentagonal_Num(n));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP Program to find nth
// Centered pentagonal number.
// Centered pentagonal number function
function centered_pentagonal_Num($n)
{
// Formula to calculate nth
// Centered pentagonal number
// and return it into main function.
return (5 * $n * $n - 5 * $n + 2) / 2;
}
// Driver Code
$n = 7;
echo $n , "th Centered pentagonal number: ";
echo centered_pentagonal_Num($n);
// This code is contributed by aj_36
?>
126
Chapter 21. Centered pentagonal number
Output :
Source
https://www.geeksforgeeks.org/centered-pentagonal-number/
127
Chapter 22
Input : 2
Output : 14
Input : 9
Output : 469
128
Chapter 22. Centered tridecagonal number
C++
Java
129
Chapter 22. Centered tridecagonal number
}
// Driver Code
public static void main (String[] args)
{
long n = 3;
System.out.println(centeredTridecagonalNum(n));
n = 10;
System.out.println(centeredTridecagonalNum(n));
}
}
// This code is contributed by anuj_67.
Python3
C#
130
Chapter 22. Centered tridecagonal number
// Function to find nth centered
// tridecagonal number
static long centeredTridecagonalNum(long n)
{
// Formula to calculate nth
// centered tridecagonal number
return (13 * n * (n - 1) + 2) / 2;
}
// Driver Code
public static void Main ()
{
long n = 3;
Console.WriteLine(centeredTridecagonalNum(n));
n = 10;
Console.WriteLine(centeredTridecagonalNum(n));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP Program to find nth
// centered tridecagonal number
// Function to find nth centered
// tridecagonal number
function centeredTridecagonalNum( $n)
{
// Formula to calculate nth
// centered tridecagonal number
return (13 * $n *
($n - 1) + 2) / 2;
}
// Driver Code
$n = 3;
echo centeredTridecagonalNum($n);
echo"\n";
$n = 10;
echo centeredTridecagonalNum($n);
// This code is contributed by anuj_67.
?>
131
Chapter 22. Centered tridecagonal number
Output :
40
586
Reference: http://oeis.org/wiki/Figurate_numbers
Improved By : vt_m, jit_t
Source
https://www.geeksforgeeks.org/centered-tridecagonal-number/
132
Chapter 23
133
Chapter 23. Chain Code for 2D Line
The chain codes could be generated by using conditional statements for each direction but
it becomes very tedious to describe for systems having large number of directions(3-D grids
can have up to 26 directions). Instead we use a hash function. The difference in X( )
and Y( ) co-ordinates of two successive points are calculated and hashed to generate the
key for the chain code between the two points.
Hash function:
Hash table:-
1 0 5 0
1 1 8 1
0 1 7 2
-1 1 6 3
-1 0 3 4
-1 -1 0 5
134
Chapter 23. Chain Code for 2D Line
0 -1 1 6
1 -1 2 7
The function does not generate the value 4 so a dummy value is stored there.
Examples:
Python3
135
Chapter 23. Chain Code for 2D Line
136
Chapter 23. Chain Code for 2D Line
DriverFunction()
Output:
Chain code for the straight line from (-9, -3) to (10, 1) is 0010000100010000100
Source
https://www.geeksforgeeks.org/chain-code-for-2d-line/
137
Chapter 24
Check if a given circle lies completely inside the ring formed by two concentric circles -
GeeksforGeeks
Given two circles of radius r and R, both have their centre at the origin. Now, given another
circle of radius r1 and centre at (x1, y1). Check, if the third circle(circle of radius r1) lies
completely inside the ring formed by two circles of radius r and R.
Examples :
Input : r = 8 R = 4
r1 = 2 x1 = 6 y1 = 0
Output : yes
Input : r = 8 R = 4
r1 = 2 x1 = 5 y1 = 0
Output : no
Important : Concentric circles are those circles which have same centre. The region lying
between two concentric circles is called annulus or the circular ring.
138
Chapter 24. Check if a given circle lies completely inside the ring formed by two
concentric circles
Example :
There are two concentric circles with their centre at origin(0, 0) and radius as r = 8 and R
= 4.
1.) Circle 1 and 2 lies inside the ring.
2.) Circle 3 and 4 are outside the ring.
The complete figure can be visualised as given below :
139
Chapter 24. Check if a given circle lies completely inside the ring formed by two
concentric circles
Approach :
This problem can be solved using Pythagoras Theorem . Compute the distance between
the centre of the circle and origin using Pythagoras theorem, suppose it is denoted by ‘dis’.
After computing the distance just check that the value of (dis – r1)> = r and (dis + r1)<
= R. If both these conditions hold then the circle lies completely inside the ring.
C++
140
Chapter 24. Check if a given circle lies completely inside the ring formed by two
concentric circles
Java
141
Chapter 24. Check if a given circle lies completely inside the ring formed by two
concentric circles
Python3
142
Chapter 24. Check if a given circle lies completely inside the ring formed by two
concentric circles
C#
// C# code to check if a
// circle lies in the ring
using System;
class ring {
// Function to check if circle
// lies in the ring
public static bool checkcircle(int r, int R,
int r1, int x1, int y1)
{
// distance between center of circle
// center of concentric circles(origin)
// using Pythagoras theorem
int dis = (int)Math.Sqrt(x1 * x1 + y1 * y1);
// Condition to check if circle
// is strictly inside the ring
return (dis - r1 >= R && dis + r1 <= r);
}
// Driver Code
public static void Main()
{
// Both circle with radius 'r'
// and 'R' have center (0, 0)
int r = 8, R = 4, r1 = 2, x1 = 6, y1 = 0;
if (checkcircle(r, R, r1, x1, y1))
Console.WriteLine("yes");
else
Console.WriteLine("no");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP code to check if a circle
// lies in the ring
// Function to check if circle
// lies in the ring
143
Chapter 24. Check if a given circle lies completely inside the ring formed by two
concentric circles
Output:
yes
Improved By : jit_t
Source
https://www.geeksforgeeks.org/check-given-circle-lies-completely-inside-ring-formed-two-concentric-circles/
144
Chapter 25
Check if a line at 45 degree can divide the plane into two equal weight parts - GeeksforGeeks
Given a set of n points (xi , yi ) in 2D coordinate. Each point has some weight wi . The
task is to check whether a line at 45 degree can be drawn so that sum of weights of points
on each side are equal.
Examples:
Input : x1 = -1, y1 = 1, w1 = 3
x2 = -2, y2 = 1, w2 = 1
x3 = 1, y3 = -1, w3 = 4
Output : Yes
Input : x1 = 1, y1 = 1, w1 = 2
x2 = -1, y2 = 1, w2 = 1
x3 = 1, y3 = -1, w3 = 2
Output : No
First, let’s try to solve above problem for a vertical line i.e if a line x = i can divide the
plane into two part such that the sum of weight at each side is equal.
Observe, multiple points with the same x-coordinate can be treated as one point with weight
equal to the sum of weights of all points with the same x-coordinate.
Now, traverse through all x-coordinates from the minimum x-coordinate to maximum x-
coordinate. So, make an array prefix_sum[], which will store the sum of weights till the
145
Chapter 25. Check if a line at 45 degree can divide the plane into two equal weight parts
point x = i.
So, there can be two options for which the answer can be ‘Yes’:
Now, to solve for a line at 45 degrees, we will rotate each point by 45 degrees.
Refer: 2D Transformation or Rotation of objects
So, point at (x, y), after 45 degree rotation will become ((x – y)/sqrt(2), (x + y)/sqrt(2)).
We can ignore the sqrt(2) since it is the scaling factor. Also, we don’t need to care about y-
coordinate after rotation because a vertical line cannot distinguish between the point having
the same x-coordinate. (x, y1 ) and (x, y2 ) will lie to the right, left or on any line of the
form x = k.
#include <bits/stdc++.h>
using namespace std;
// Checking if a plane can be divide by a line
// at 45 degrees such that weight sum is equal
void is_partition_possible(int n, int x[],
int y[], int w[])
{
map<int, int> weight_at_x;
int max_x = -2e3, min_x = 2e3;
// Rotating each point by 45 degrees and
// calculating prefix sum.
// Also, finding maximum and minimum x
// coordinates
for (int i = 0; i < n; i++) {
int new_x = x[i] - y[i];
max_x = max(max_x, new_x);
min_x = min(min_x, new_x);
// storing weight sum upto x - y point
weight_at_x[new_x] += w[i];
146
Chapter 25. Check if a line at 45 degree can divide the plane into two equal weight parts
}
vector<int> sum_till;
sum_till.push_back(0);
// Finding prefix sum
for (int x = min_x; x <= max_x; x++) {
sum_till.push_back(sum_till.back() +
weight_at_x[x]);
}
int total_sum = sum_till.back();
int partition_possible = false;
for (int i = 1; i < sum_till.size(); i++) {
if (sum_till[i] == total_sum - sum_till[i])
partition_possible = true;
// Line passes through i, so it neither
// falls left nor right.
if (sum_till[i - 1] == total_sum - sum_till[i])
partition_possible = true;
}
printf(partition_possible ? "YES\n" : "NO\n");
}
// Driven Program
int main()
{
int n = 3;
int x[] = { -1, -2, 1 };
int y[] = { 1, 1, -1 };
int w[] = { 3, 1, 4 };
is_partition_possible(n, x, y, w);
return 0;
}
Output
Yes
Source
https://www.geeksforgeeks.org/check-if-a-line-at-45-degree-can-divide-the-plane-into-two-equal-weight-parts/
147
Chapter 26
Examples:
148
Chapter 26. Check if a line passes through the origin
Approach: Equation of a line passing through two points (x1, y1) and (x2, y2) is given by
y-y1 = ((y2-y1) / (x2-x1))(x-x1) + c
If line is also passing through origin, then c=0, so equation of line becomes
y-y1 = ((y2-y1) / (x2-x1))(x-x1)
Keeping x=0, y=0 in the above equation we get,
x1(y2-y1) = y1(x2-x1)
So above equation must be satisfied if any line passing through two coordinates (x1, y1) and
(x2, y2) also passes through origin (0, 0).
C++
Java
149
Chapter 26. Check if a line passes through the origin
}
// Driver code
public static void main (String[] args)
{
if (checkOrigin(1, 28, 2, 56) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Ajit.
Python3
C#
150
Chapter 26. Check if a line passes through the origin
PHP
<?php
// PHP program to find if
// line passing through
// two coordinates also
// passes through origin
// or not
function checkOrigin($x1, $y1,
$x2, $y2)
{
return ($x1 * ($y2 - $y1) ==
$y1 * ($x2 - $x1));
}
// Driver code
if (checkOrigin(1, 28, 2, 56) == true)
echo("Yes");
else
echo("No");
// This code is contributed by Ajit.
?>
Output:
Yes
Improved By : jit_t
Source
https://www.geeksforgeeks.org/check-line-passes-origin/
151
Chapter 27
Note: General equation of a line is a*x + b*y + c = 0, so only constant a, b, c are given in
the input.
Examples :
152
Chapter 27. Check if a line touches or intersects a circle
The idea is to compare the perpendicular distance between center of circle and line with the
radius of the circle.
Algorithm:
1. Find the perpendicular (say p) between center of circle and given line.
2. Compare this distance p with radius r.
……a) If p > r, then line lie outside the circle.
……b) If p = r, then line touches the circle.
……c) If p < r, then line intersect the circle.
How to find the perpendicular distance ?
Distance of a line from a point can be computed using below formula:
C++
153
Chapter 27. Check if a line touches or intersects a circle
Java
154
Chapter 27. Check if a line touches or intersects a circle
checkCollision(a, b, c, x, y, radius);
}
}
// This article is contributed by vt_m.
Python3
C#
155
Chapter 27. Check if a line touches or intersects a circle
class GFG {
static void checkCollision(int a, int b, int c,
int x, int y, int radius)
{
// Finding the distance of line from center.
double dist = (Math.Abs(a * x + b * y + c)) /
Math.Sqrt(a * a + b * b);
// Checking if the distance is less than,
// greater than or equal to radius.
if (radius == dist)
Console.WriteLine ("Touch");
else if (radius > dist)
Console.WriteLine("Intersect");
else
Console.WriteLine("Outside");
}
// Driven Program
public static void Main ()
{
int radius = 5;
int x = 0, y = 0;
int a = 3, b = 4, c = 25;
checkCollision(a, b, c, x, y, radius);
}
}
// This article is contributed by vt_m.
PHP
<?php
// PHP program to check if a line
// touches or intersects or outside
// a circle.
function checkCollision($a, $b, $c,
$x, $y, $radius)
{
// Finding the distance
// of line from center.
$dist = (abs($a * $x + $b * $y + $c)) /
sqrt($a * $a + $b * $b);
156
Chapter 27. Check if a line touches or intersects a circle
// Checking if the distance is less than,
// greater than or equal to radius.
if ($radius == $dist)
echo "Touch";
else if ($radius > $dist)
echo "Intersect";
else
echo "Outside" ;
}
// Driver Code
$radius = 5;
$x = 0;
$y = 0;
$a = 3;
$b = 4;
$c = 25;
checkCollision($a, $b, $c, $x, $y, $radius);
// This code is contributed by Sam007
?>
Output :
Touch
Improved By : Sam007
Source
https://www.geeksforgeeks.org/check-line-touches-intersects-circle/
157
Chapter 28
This problem is already discussed in a previous post. In this post we have discussed a new
approach.
Approach: The above problem can be solved by observation. A point lies inside or not the
rectangle if and only if it’s x-coordinate lies between the x-coordinate of the given bottom-
right and top-left coordinates of the rectangle and y-coordinate lies between the y-coordinate
of the given bottom-right and top-left coordinates.
Below is the implementation of the above approach:
C++
158
Chapter 28. Check if a point lies on or inside a rectangle | Set-2
Java
// Java program to Check if
// a point lies on or inside
// a rectangle | Set-2
class GFG
{
// function to find if given point
// lies inside a given rectangle or not.
static boolean FindPoint(int x1, int y1, int x2,
int y2, int x, int y)
{
if (x > x1 && x < x2 && y > y1 && y < y2) return true; return false; } // Driver code
public static void main(String[] args) { // bottom-left and top-right // corners of rectangle
int x1 = 0, y1 = 0, x2 = 10, y2 = 8; // given point int x = 1, y = 5; // function call if
(FindPoint(x1, y1, x2, y2, x, y)) System.out.println(”Yes”); else System.out.println(”No”);
} } // This code is contributed // by ChitraNayal [tabby title=”Python3”]
159
Chapter 28. Check if a point lies on or inside a rectangle | Set-2
C#
// C# program to Check if a
// point lies on or inside
// a rectangle | Set-2
using System;
class GFG
{
// function to find if given
// point lies inside a given
// rectangle or not.
static bool FindPoint(int x1, int y1, int x2,
160
Chapter 28. Check if a point lies on or inside a rectangle | Set-2
<?php
// PHP program to Check if
// a point lies on or inside
// a rectangle | Set-2
// function to find if given
// point lies inside a given
// rectangle or not.
function FindPoint($x1, $y1, $x2,
$y2, $x, $y)
{
if ($x > $x1 and $x < $x2 and
$y > $y1 and $y < $y2)
return true;
return false;
}
// Driver code
// bottom-left and top-right
// corners of rectangle
$x1 = 0; $y1 = 0;
$x2 = 10; $y2 = 8;
// given point
$x = 1; $y = 5;
// function call
if (FindPoint($x1, $y1, $x2,
$y2, $x, $y))
echo "Yes";
else
echo "No";
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>
Output:
161
Chapter 28. Check if a point lies on or inside a rectangle | Set-2
Yes
Source
https://www.geeksforgeeks.org/check-if-a-point-lies-on-or-inside-a-rectangle-set-2/
162
Chapter 29
This problem is mainly an extension of How to check if given four points form a square
We can solve this problem by using properties of a rectangle. First, we check total unique
end points of segments, if count of these points is not equal to 4 then the line segment
can’t make a rectangle. Then we check distances between all pair of points, there should
163
Chapter 29. Check if four segments form a rectangle
be at most 3 different distances, one for diagonal and two for sides and at the end we will
check the relation among these three distances, for line segments to make a rectangle these
distance should satisfy Pythagorean relation because sides and diagonal of rectangle makes
a right angle triangle. If they satisfy mentioned conditions then we will flag polygon made
by line segment as rectangle otherwise not.
164
Chapter 29. Check if four segments form a rectangle
// calculating distance between all pair of
// end points of line segments
for (auto it1=st.begin(); it1!=st.end(); it1++)
for (auto it2=st.begin(); it2!=st.end(); it2++)
if (*it1 != *it2)
dist.insert(getDis(*it1, *it2));
// if total unique distance are more than 3,
// then line segment can't make a rectangle
if (dist.size() > 3)
return false;
// copying distance into array. Note that set maintains
// sorted order.
int distance[3];
int i = 0;
for (auto it = dist.begin(); it != dist.end(); it++)
distance[i++] = *it;
// If line seqments form a square
if (dist.size() == 2)
return (2*distance[0] == distance[1]);
// distance of sides should satisfy pythagorean
// theorem
return (distance[0] + distance[1] == distance[2]);
}
// Driver code to test above methods
int main()
{
Segment segments[] =
{
{4, 2, 7, 5},
{2, 4, 4, 2},
{2, 4, 5, 7},
{5, 7, 7, 5}
};
(isPossibleRectangle(segments))?cout << "Yes\n":cout << "No\n";
}
Output:
Yes
Improved By : harrypotter0
165
Chapter 29. Check if four segments form a rectangle
Source
https://www.geeksforgeeks.org/check-four-segments-form-rectangle/
166
Chapter 30
Input : 1 1 2 2
Output : Yes
Input : 1 2 3 4
Output : No
Approach 1 :- We will check, if any of the two integers are equal and make sure rest of
two are also equal using few if else conditions.
C++
167
Chapter 30. Check if given four integers (or sides) make rectangle
if (a == b == c == d)
return true;
else if (a == b && c == d)
return true;
else if (a == d && c == b)
return true;
else if (a == c && d == b)
return true;
else
return false;
}
// Driver code
int main()
{
int a, b, c, d;
a = 1, b = 2, c = 3, d = 4;
if (isRectangle(a, b, c, d))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
168
Chapter 30. Check if given four integers (or sides) make rectangle
return true;
else
return false;
}
// Driver code
public static void main(String[] args)
{
int a = 1, b = 2, c = 3, d = 4;
if (isRectangle(a, b, c, d))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by prerna saini.
Python3
169
Chapter 30. Check if given four integers (or sides) make rectangle
# This code is contributed by Ansu Kumari.
C#
170
Chapter 30. Check if given four integers (or sides) make rectangle
Output :
No
C++
Java
171
Chapter 30. Check if given four integers (or sides) make rectangle
int c, int d)
{
if ((a ^ b ^ c ^ d) != 0)
return false;
else
return true;
}
// Driver code
public static void main(String[] args)
{
int a, b, c, d;
a = 3; b = 2; c = 3; d = 2;
if (isRectangle(a, b, c, d))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by
// Smitha Dinesh Semwal
Python3
C#
172
Chapter 30. Check if given four integers (or sides) make rectangle
Output :
Yes
Source
https://www.geeksforgeeks.org/check-given-four-integers-sides-make-rectangle/
173
Chapter 31
Input: angle = 90
Output: YES
Polygons with sides 4 is
possible with angle 90 degrees.
Input: angle = 30
Output: NO
Approach: The Interior angle is defined as the angle between any two adjacent sides of a
regular polygon.
174
Chapter 31. Check if it is possible to create a polygon with a given angle
C++
Java
class GFG
{
// Function to check whether
// it is possible to make a
// regular polygon with a given angle.
static void makePolygon(double a)
{
// N denotes the number of
// sides of polygons possible
double n = 360 / (180 - a);
if (n == (int)n)
System.out.println("YES");
else
System.out.println("NO");
}
175
Chapter 31. Check if it is possible to create a polygon with a given angle
// Driver code
public static void main (String[] args)
{
double a = 90;
// function to print
// the required answer
makePolygon(a);
}
}
// This code is contributed by Bilal
Python3
# Python 3 implementation
# of above approach
# Function to check whether
# it is possible to make a
# regular polygon with a
# given angle.
def makePolygon(a) :
# N denotes the number of sides
# of polygons possible
n = 360 / (180 - a)
if n == int(n) :
print("YES")
else :
print("NO")
# Driver Code
if __name__ == "__main__" :
a = 90
# function calling
makePolygon(a)
# This code is contributed
# by ANKITRAI1
C#
// C# implementation of
176
Chapter 31. Check if it is possible to create a polygon with a given angle
// above approach
using System;
class GFG
{
// Function to check whether
// it is possible to make a
// regular polygon with a
// given angle.
static void makePolygon(double a)
{
// N denotes the number of
// sides of polygons possible
double n = 360 / (180 - a);
if (n == (int)n)
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
// Driver code
static void Main()
{
double a = 90;
// function to print
// the required answer
makePolygon(a);
}
}
// This code is contributed by mits
PHP
Output:
YES
Source
https://www.geeksforgeeks.org/check-if-it-is-possible-to-create-a-polygon-with-a-given-angle/
177
Chapter 32
Check if right triangle possible from given area and hypotenuse - GeeksforGeeks
Given area and hypotenuse, the aim is to print all sides if right triangle can exist, else print
-1. We need to print all sides in ascending order.
Examples:
Input : 6 5
Output : 3 4 5
Input : 10 6
Output : -1
C++
178
Chapter 32. Check if right triangle possible from given area and hypotenuse
Java
179
Chapter 32. Check if right triangle possible from given area and hypotenuse
Python
180
Chapter 32. Check if right triangle possible from given area and hypotenuse
if D >= 0:
# applying the linear equation
# formula to find both the roots
root1 = (H * H + sqrt(D))/2
root2 = (H * H - sqrt(D))/2
a = sqrt(root1)
b = sqrt(root2)
if b >= a:
print a, b, H
else:
print b, a, H
else:
print "-1"
# Driver code
# Area is 6 and hypotenuse is 5.
findRightAngle(6, 5)
C#
181
Chapter 32. Check if right triangle possible from given area and hypotenuse
PHP
<?php
// PHP program to check existence of
// right triangle.
// Prints three sides of a right trianlge
// from given area and hypotenuse if
// triangle is possible, else prints -1.
function findRightAngle($A, $H)
{
// Descriminant of the equation
$D = pow($H, 4) - 16 * $A * $A;
if ($D >= 0)
{
// applying the linear equation
// formula to find both the roots
$root1 = ($H * $H + sqrt($D)) / 2;
$root2 = ($H * $H - sqrt($D)) / 2;
$a = sqrt($root1);
$b = sqrt($root2);
if ($b >= $a)
echo $a , " ", $b , " " , $H;
else
echo $b , " " , $a , " " , $H;
}
182
Chapter 32. Check if right triangle possible from given area and hypotenuse
else
echo "-1";
}
// Driver code
findRightAngle(6, 5);
// This code is contributed By Anuj_67
?>
Output:
3 4 5
Improved By : vt_m
Source
https://www.geeksforgeeks.org/check-right-angles-possible-given-area-hypotenuse/
183
Chapter 33
Input : a1 = 2, b1 = -3, c1 = 5
a2 = 3, b2 = 4, c2 = -7
a3 = 9, b3 = -5, c3 = 8
Output : Yes
Input : a1 = 2, b1 = -3, c1 = 5
a2 = 3, b2 = 4, c2 = -7
a3 = 9, b3 = -5, c3 = 4
Output : No
Let
a1 x + b1 y + c1 = 0 ………. (1)
a2 x + b2 y + c2 = 0 ………. (2)
a3 x + b3 y + c3 = 0 ………. (3)
Suppose the eqn (i) and (ii) intersets at (x1 , y1 ). Then (x1 , y1 ) will satisfy bothe equations.
Therefore, solving (i) and (ii) using method of cross-multiplication, we get,
(x1 /b1 c2 – b2 c1 ) = (y1 /c1 a2 – c2 a1 ) = (1/a1 b2 – a2 b1 )
184
Chapter 33. Check if three straight lines are concurrent or not
Therefore,
x1 = (b1 c2 – b2 c1 /a1 b2 – a2 b1 ) and
y1 = (c1 a2 – c2 a1 /a1 b2 – a2 b1 ), a1 b2 – a2 b1 != 0
Therefore, the required coodinates of the point of intersection of the lines (i) and (ii) are
(b1 c2 – b2 c1 /a1 b2 – a2 b1 , c1 a2 – c2 a1 /a1 b2 – a2 b1 )
For, three of line to be concurrent, (x1 , y1 ) must satisfy the equation (iii) as well.
So,
a3 x + b3 y + c3 = 0
=> a3 (b1 c2 – b2 c1 /a1 b2 – a2 b1 ) + b3 (c1 a2 – c2 a1 /a1 b2 – a2 b1 ) + c3 = 0
=> a3 (b1 c2 – b2 c1 ) + b3 (c1 a2 – c2 a1 ) + c3 (a1 b2 – a2 b1 ) = 0
So, we only need to check if above condition satisfy or not.
Below is the implemenatation of this approach:
C++
Java
185
Chapter 33. Check if three straight lines are concurrent or not
Python 3
186
Chapter 33. Check if three straight lines are concurrent or not
# Driven Program
a1 = 2
b1 = -3
c1 = 5
a2 = 3
b2 = 4
c2 = -7
a3 = 9
b3 = -5
c3 = 8
if(checkConcurrent(a1, b1, c1, a2, b2, c2,
a3, b3, c3)):
print("Yes")
else:
print("No")
# This code is contributed by Smitha
C#
187
Chapter 33. Check if three straight lines are concurrent or not
Console.WriteLine( "Yes");
else
Console.WriteLine( "No");
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP Program to check if three straight
// line are concurrent or not
// Return true if three line are
// concurrent, else false.
function checkConcurrent($a1, $b1, $c1,
$a2, $b2, $c2,
$a3, $b3, $c3)
{
return ($a3 * ($b1 * $c2 - $b2 * $c1) +
$b3 * ($c1 * $a2 - $c2 * $a1) +
$c3 * ($a1 * $b2 - $a2 * $b1) == 0);
}
// Driver Code
$a1 = 2; $b1 = -3; $c1 = 5;
$a2 = 3; $b2 = 4; $c2 = -7;
$a3 = 9; $b3 = -5; $c3 = 8;
if(checkConcurrent($a1, $b1, $c1, $a2, $b2,
$c2, $a3, $b3, $c3))
echo "Yes";
else
echo "No";
// This code is contributed by anuj_67.
?>
Output:
Yes
188
Chapter 33. Check if three straight lines are concurrent or not
Source
https://www.geeksforgeeks.org/check-three-straight-lines-concurrent-not/
189
Chapter 34
Input : C1 = (3, 4)
C2 = (14, 18)
R1 = 5, R2 = 8
Output : Circles do not touch each other.
Input : C1 = (2, 3)
C2 = (15, 28)
R1 = 12, R2 = 10
Output : Circles intersect with each other.
Input : C1 = (-10, 8)
C2 = (14, -24)
R1 = 30, R2 = 10
Input : -10 8
14 -24
30 10
Output : Circle touch each other.
190
Chapter 34. Check if two given circles touch or intersect each other
1. If C1C2 == R1 + R2
Circle A and B are touch to each other.
2. If C1C2 > R1 + R2
Circle A and B are not touch to each other.
3. If C1C2 < R1 + R2
Circle intersects each other.
C++
191
Chapter 34. Check if two given circles touch or intersect each other
Java
Python3
# Python3 program to
192
Chapter 34. Check if two given circles touch or intersect each other
C#
193
Chapter 34. Check if two given circles touch or intersect each other
PHP
<?php
// PHP program to check if two
// circles touch each other or not.
function circle($x1, $y1, $x2,
$y2, $r1, $r2)
{
$distSq = ($x1 - $x2) * ($x1 - $x2) +
($y1 - $y2) * ($y1 - $y2);
$radSumSq = ($r1 + $r2) * ($r1 + $r2);
if ($distSq == $radSumSq)
return 1;
else if ($distSq > $radSumSq)
return -1;
else
194
Chapter 34. Check if two given circles touch or intersect each other
return 0;
}
// Driver code
$x1 = -10; $y1 = 8;
$x2 = 14; $y2 = -24;
$r1 = 30; $r2 = 10;
$t = circle($x1, $y1, $x2,
$y2, $r1, $r2);
if ($t == 1)
echo "Circle touch to each other.";
else if ($t < 0)
echo "Circle not touch to each other.";
else
echo "Circle intersect to each other.";
// This code is contributed by vt_m.
?>
Output :
Improved By : vt_m
Source
https://www.geeksforgeeks.org/check-two-given-circles-touch-intersect/
195
Chapter 35
196
Chapter 35. Check whether a given point lies inside a rectangle or not
#include <bits/stdc++.h>
using namespace std;
/* A utility function to calculate area of
triangle formed by (x1, y1), (x2, y2) and
(x3, y3) */
float area(int x1, int y1, int x2, int y2,
int x3, int y3)
{
return abs((x1 * (y2 - y3) + x2 * (y3 - y1) +
x3 * (y1 - y2)) / 2.0);
}
/* A function to check whether point P(x, y)
lies inside the rectangle formed by A(x1, y1),
B(x2, y2), C(x3, y3) and D(x4, y4) */
bool check(int x1, int y1, int x2, int y2, int x3,
int y3, int x4, int y4, int x, int y)
{
/* Calculate area of rectangle ABCD */
float A = area(x1, y1, x2, y2, x3, y3) +
area(x1, y1, x4, y4, x3, y3);
/* Calculate area of triangle PAB */
float A1 = area(x, y, x1, y1, x2, y2);
/* Calculate area of triangle PBC */
float A2 = area(x, y, x2, y2, x3, y3);
/* Calculate area of triangle PCD */
float A3 = area(x, y, x3, y3, x4, y4);
/* Calculate area of triangle PAD */
float A4 = area(x, y, x1, y1, x4, y4);
/* Check if sum of A1, A2, A3 and A4
is same as A */
return (A == A1 + A2 + A3 + A4);
}
/* Driver program to test above function */
197
Chapter 35. Check whether a given point lies inside a rectangle or not
int main()
{
/* Let us check whether the point P(10, 15)
lies inside the rectangle formed by A(0, 10),
B(10, 0) C(0, -10) D(-10, 0) */
if (check(0, 10, 10, 0, 0, -10, -10, 0, 10, 15))
cout << "yes";
else
cout << "no";
return 0;
}
Java
class GFG
{
/* A utility function to calculate area of
triangle formed by (x1, y1), (x2, y2) and
(x3, y3) */
static float area(int x1, int y1, int x2,
int y2, int x3, int y3)
{
return (float)Math.abs((x1 * (y2 - y3) +
x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);
}
/* A function to check whether point P(x, y)
lies inside the rectangle formed by A(x1, y1),
B(x2, y2), C(x3, y3) and D(x4, y4) */
static boolean check(int x1, int y1, int x2, int y2,
int x3, int y3, int x4, int y4, int x, int y)
{
/* Calculate area of rectangle ABCD */
float A = area(x1, y1, x2, y2, x3, y3)+
area(x1, y1, x4, y4, x3, y3);
/* Calculate area of triangle PAB */
float A1 = area(x, y, x1, y1, x2, y2);
/* Calculate area of triangle PBC */
float A2 = area(x, y, x2, y2, x3, y3);
/* Calculate area of triangle PCD */
float A3 = area(x, y, x3, y3, x4, y4);
/* Calculate area of triangle PAD */
float A4 = area(x, y, x1, y1, x4, y4);
198
Chapter 35. Check whether a given point lies inside a rectangle or not
/* Check if sum of A1, A2, A3 and A4
is same as A */
return (A == A1 + A2 + A3 + A4);
}
// Driver code
public static void main (String[] args)
{
/* Let us check whether the point P(10, 15)
lies inside the rectangle formed by A(0, 10),
B(10, 0) C(0, -10) D(-10, 0) */
if (check(0, 10, 10, 0, 0, -10, -10, 0, 10, 15))
System.out.print("yes");
else
System.out.print("no");
}
}
// This code is contributed by Anant Agarwal.
C#
199
Chapter 35. Check whether a given point lies inside a rectangle or not
// Calculate area of rectangle ABCD
float A = area(x1, y1, x2, y2, x3, y3) +
area(x1, y1, x4, y4, x3, y3);
// Calculate area of triangle PAB
float A1 = area(x, y, x1, y1, x2, y2);
// Calculate area of triangle PBC
float A2 = area(x, y, x2, y2, x3, y3);
// Calculate area of triangle PCD
float A3 = area(x, y, x3, y3, x4, y4);
// Calculate area of triangle PAD
float A4 = area(x, y, x1, y1, x4, y4);
// Check if sum of A1, A2, A3
// and A4is same as A
return (A == A1 + A2 + A3 + A4);
}
// Driver code
public static void Main ()
{
// Let us check whether the point
// P(10, 15) lies inside the rectangle
// formed by A(0, 10), B(10, 0),
// C(0, -10), D(-10, 0)
if (check(0, 10, 10, 0, 0, -10, -10, 0, 10, 15))
Console.Write("yes");
else
Console.Write("no");
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to check whether a
// given point lies inside a
// rectangle or not
// A utility function to
// calculate area of
200
Chapter 35. Check whether a given point lies inside a rectangle or not
201
Chapter 35. Check whether a given point lies inside a rectangle or not
// D(-10, 0)
if (check(0, 10, 10, 0, 0, -10,
-10, 0, 10, 15))
echo "yes";
else
echo "no";
// This code is contributed by vt_m.
?>
Output:
no
Source
https://www.geeksforgeeks.org/check-whether-given-point-lies-inside-rectangle-not/
202
Chapter 36
B(10,30)
/ \
/ \
/ \
/ P \ P'
/ \
A(0,0) ----------- C(20,0)
Solution:
Let the coordinates of three corners be (x1, y1), (x2, y2) and (x3, y3). And coordinates of
the given point P be (x, y)
1) Calculate area of the given triangle, i.e., area of the triangle ABC in the above diagram.
Area A = [ x1(y2 – y3) + x2(y3 – y1) + x3(y1-y2)]/2
2) Calculate area of the triangle PAB. We can use the same formula for this. Let this area
be A1.
3) Calculate area of the triangle PBC. Let this area be A2.
4) Calculate area of the triangle PAC. Let this area be A3.
5) If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.
C++
203
Chapter 36. Check whether a given point lies inside a triangle or not
#include <bits/stdc++.h>
using namespace std;
/* A utility function to calculate area of triangle formed by (x1, y1),
(x2, y2) and (x3, y3) */
float area(int x1, int y1, int x2, int y2, int x3, int y3)
{
return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0);
}
/* A function to check whether point P(x, y) lies inside the triangle formed
by A(x1, y1), B(x2, y2) and C(x3, y3) */
bool isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)
{
/* Calculate area of triangle ABC */
float A = area (x1, y1, x2, y2, x3, y3);
/* Calculate area of triangle PBC */
float A1 = area (x, y, x2, y2, x3, y3);
/* Calculate area of triangle PAC */
float A2 = area (x1, y1, x, y, x3, y3);
/* Calculate area of triangle PAB */
float A3 = area (x1, y1, x2, y2, x, y);
/* Check if sum of A1, A2 and A3 is same as A */
return (A == A1 + A2 + A3);
}
/* Driver program to test above function */
int main()
{
/* Let us check whether the point P(10, 15) lies inside the triangle
formed by A(0, 0), B(20, 0) and C(10, 30) */
if (isInside(0, 0, 20, 0, 10, 30, 10, 15))
printf ("Inside");
else
printf ("Not Inside");
return 0;
}
Java
204
Chapter 36. Check whether a given point lies inside a triangle or not
class GFG {
/* A utility function to calculate area of triangle
formed by (x1, y1) (x2, y2) and (x3, y3) */
static double area(int x1, int y1, int x2, int y2,
int x3, int y3)
{
return Math.abs((x1*(y2-y3) + x2*(y3-y1)+
x3*(y1-y2))/2.0);
}
/* A function to check whether point P(x, y) lies
inside the triangle formed by A(x1, y1),
B(x2, y2) and C(x3, y3) */
static boolean isInside(int x1, int y1, int x2,
int y2, int x3, int y3, int x, int y)
{
/* Calculate area of triangle ABC */
double A = area (x1, y1, x2, y2, x3, y3);
/* Calculate area of triangle PBC */
double A1 = area (x, y, x2, y2, x3, y3);
/* Calculate area of triangle PAC */
double A2 = area (x1, y1, x, y, x3, y3);
/* Calculate area of triangle PAB */
double A3 = area (x1, y1, x2, y2, x, y);
/* Check if sum of A1, A2 and A3 is same as A */
return (A == A1 + A2 + A3);
}
/* Driver program to test above function */
public static void main(String[] args)
{
/* Let us check whether the point P(10, 15)
lies inside the triangle formed by
A(0, 0), B(20, 0) and C(10, 30) */
if (isInside(0, 0, 20, 0, 10, 30, 10, 15))
System.out.println("Inside");
else
System.out.println("Not Inside");
}
}
205
Chapter 36. Check whether a given point lies inside a triangle or not
Python
206
Chapter 36. Check whether a given point lies inside a triangle or not
C#
207
Chapter 36. Check whether a given point lies inside a triangle or not
Console.WriteLine("Inside");
else
Console.WriteLine("Not Inside");
}
}
// This code is contributed by vt_m.
PHP
<?php
/* A utility function to calculate
area of triangle formed by (x1, y1),
(x2, y2) and (x3, y3) */
function area($x1, $y1, $x2,
$y2, $x3, $y3)
{
return abs(($x1 * ($y2 - $y3) +
$x2 * ($y3 - $y1) +
$x3 * ($y1 - $y2)) / 2.0);
}
/* A function to check whether
P(x, y) lies inside the
triangle formed by A(x1, y1),
B(x2, y2) and C(x3, y3) */
function isInside($x1, $y1, $x2, $y2,
$x3, $y3, $x, $y)
{
/* Calculate area of triangle ABC */
$A = area ($x1, $y1, $x2, $y2, $x3, $y3);
/* Calculate area of triangle PBC */
$A1 = area ($x, $y, $x2, $y2, $x3, $y3);
/* Calculate area of triangle PAC */
$A2 = area ($x1, $y1, $x, $y, $x3, $y3);
/* Calculate area of triangle PAB */
$A3 = area ($x1, $y1, $x2, $y2, $x, $y);
/* Check if sum of A1, A2
and A3 is same as A */
return ($A == $A1 + $A2 + $A3);
}
208
Chapter 36. Check whether a given point lies inside a triangle or not
Ouptut:
Inside
Exercise: Given coordinates of four corners of a rectangle, and a point P. Write a function
to check whether P lies inside the given rectangle or not.
Improved By : vt_m
Source
https://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/
209
Chapter 37
Check whether a given point lies on or inside the rectangle | Set 3 - GeeksforGeeks
Given two numbers a and b where b < a form a rectangle with points (0, b), (b, 0), (a-b,
b), (b, a-b). Given a point (x, y), the task is to check whether this point lies inside or on
the rectangle or not.
Examples:
Input: a = 7, b = 2, x = 5, y = 2;
Output: Given point does not lie on the rectangle
Input: a = 7, b = 2, x = 4, y = 5;
Output: Given point lies inside the rectangle
1. The right sideline ( x-y-b = 0 ) must give the value less than or equals to zero.
2. The left sideline ( x-y+a = 0 ) must give the value greater than or equals to one.
3. The upper sideline ( x+y-2*a+b = 0 ) must give the value less than or equals to
zero.
4. The lower sideline ( x+y-b = 0 ) must give the value greater than or equals to one.
C++
210
Chapter 37. Check whether a given point lies on or inside the rectangle | Set 3
Java
// Java program to Check whether
// a given point lies inside or
// on the rectangle or not
class GFG
{
// function to Check whether
// a given point lies inside
// or on the rectangle or not
static boolean LiesInsieRectangle(int a, int b,
int x, int y)
{
if (x – y – b <= 0 && x - y + b >= 0 &&
x + y – 2 * a + b <= 0 && x + y - b >= 0)
return true;
return false;
}
// Driver code
public static void main(String[] args)
211
Chapter 37. Check whether a given point lies on or inside the rectangle | Set 3
{
int a = 7, b = 2, x = 4, y = 5;
if (LiesInsieRectangle(a, b, x, y))
System.out.println(“Given point lies ” +
“inside the rectangle”);
else
System.out.println(“Given point does not ” +
“lie on the rectangle”);
}
}
// This code is contributed
// by ChitraNayal
Python3
C#
212
Chapter 37. Check whether a given point lies on or inside the rectangle | Set 3
<?php
// PHP program to Check whether
// a given point lies inside
// or on the rectangle or not
// function to Check whether
// a given point lies inside
// or on the rectangle or not
function LiesInsieRectangle($a, $b,
$x, $y)
{
if ($x - $y - $b <= 0 &&
213
Chapter 37. Check whether a given point lies on or inside the rectangle | Set 3
Output:
Source
https://www.geeksforgeeks.org/check-whether-a-given-point-lies-on-or-inside-the-rectangle-set-3/
214
Chapter 38
Input : Radius = 8
StartAngle = 0
Percentage = 12
x = 3 y = 4
Output : Point (3, 4) exists in the circle
sector
Input : Radius = 12
Startangle = 45
Percentage = 25
x = 3 y = 4
Output : Point (3, 4) does not exist in
the circle sector
215
Chapter 38. Check whether a point exists in circle sector or not.
Source:wikibooks.org
In this image starting angle is 0 degree, radius r and suppose that percentage of colored
area is 12% then we calculate Ending Angle as 360/percentage + starting angle.
To find whether a point (x, y) exists in a circle sector (centered at origin) or not we find
polar coordinates of that point and then go through the following steps:
C++
216
Chapter 38. Check whether a point exists in circle sector or not.
// or not
if (Angle>=startAngle && Angle<=endAngle && polarradius<radius)
printf("Point (%d, %d) exist in the circle sector\n", x, y);
else
printf("Point (%d, %d) does not exist in the circle sector\n",
x, y);
}
// Driver code
int main()
{
int radius = 8, x = 3, y = 4;
float percent = 12, startAngle = 0;
checkPoint(radius, x, y, percent, startAngle);
return 0;
}
Java
217
Chapter 38. Check whether a point exists in circle sector or not.
// Driver Program to test above function
public static void main(String arg[])
{
int radius = 8, x = 3, y = 4;
float percent = 12, startAngle = 0;
checkPoint(radius, x, y, percent, startAngle);
}
}
// This code is contributed
// by Anant Agarwal.
Python3
218
Chapter 38. Check whether a point exists in circle sector or not.
C#
Output :
219
Chapter 38. Check whether a point exists in circle sector or not.
Source
https://www.geeksforgeeks.org/check-whether-point-exists-circle-sector-not/
220
Chapter 39
Approach:
Whether a point lies inside a sphere or not, depends upon its distance from the centre.
A point (x, y, z) is inside the sphere with center (cx, cy, cz) and radius r if
A point (x, y, z) lies on the sphere with center (cx, cy, cz) and radius r if
221
Chapter 39. Check whether a point lies inside a sphere or not
A point (x, y, z) is outside the sphere with center (cx, cy, cz) and radius r if
C++
222
Chapter 39. Check whether a point lies inside a sphere or not
Java
223
Chapter 39. Check whether a point lies inside a sphere or not
Python
224
Chapter 39. Check whether a point lies inside a sphere or not
C#
// C# code to illustrate
// above approach
using System;
class GFG
{
// function to calculate
// the distance between
// centre and the point
public static int check(int cx, int cy,
int cz, int x,
int y, int z)
{
int x1 = (int)Math.Pow((x - cx), 2);
int y1 = (int)Math.Pow((y - cy), 2);
int z1 = (int)Math.Pow((z - cz), 2);
// distance between the
// centre and given point
return (x1 + y1 + z1);
}
// Driver Code
public static void Main()
{
// coordinates of centre
int cx = 1, cy = 2, cz = 3;
int r = 5; // radius of the sphere
// coordinates of point
int x = 4, y = 5, z = 2;
int ans = check(cx, cy, cz,
x, y, z);
// distance btw centre
// and point is less
// than radius
if (ans < (r * r))
Console.WriteLine("Point is inside" +
" the sphere");
// distance btw centre
// and point is
225
Chapter 39. Check whether a point lies inside a sphere or not
PHP
<?php
// function to calculate
// the distance between
// centre and the point
function check($cx, $cy, $cz,
$x, $y, $z)
{
$x1 = pow(($x - $cx), 2);
$y1 = pow(($y - $cy), 2);
$z1 = pow(($z - $cz), 2);
// distance between the
// centre and given point
return ($x1 + $y1 + $z1);
}
// Driver Code
// coordinates of centre
$cx = 1;
$cy = 2;
$cz = 3;
$r = 5; // radius of the sphere
$x = 4;
$y = 5;
$z = 2; // coordinates of point
$ans = check($cx, $cy, $cz,
$x, $y, $z);
226
Chapter 39. Check whether a point lies inside a sphere or not
// distance btw centre and
// point is less than radius
if ($ans < ($r * $r))
echo "Point is inside " .
"the sphere";
// distance btw centre and
// point is equal to radius
else if ($ans == ($r * $r))
echo "Point lies on the sphere";
// distance btw center and point
// is greater than radius
else
echo "Point is outside " .
"the sphere";
// This code is contributed
// by shiv_bhakt
?>
Output:
Time Complexity:O(1)
Improved By : vt_m, shiv_bhakt
Source
https://www.geeksforgeeks.org/check-whether-a-point-lies-inside-a-sphere-or-not/
227
Chapter 40
A parallelogram has four sides. Two opposite sides are parallel and are of same lengths.
Examples:
Problems for checking square and rectangle can be read from Square checking and Rectangle
checking but in this problem, we need to check for the parallelogram. The main properties
of the parallelogram are that opposite sides of parallelogram are parallel and of equal length
228
Chapter 40. Check whether four points make a parallelogram
and diagonals of parallelogram bisect each other. We use the second property to solve this
problem. As there are four points, we can get total 6 midpoints by considering each pair.
Now for four points to make a parallelogram, 2 of the midpoints should be equal and rest
of them should be different.
In below code, we have created a map, which stores pairs corresponding to each midpoint.
After calculating all midpoints, we have iterated over the map and check the occurrence of
each midpoint, If exactly one midpoint occurred twice and other have occurred once, then
given four points make a parallelogram otherwise not.
229
Chapter 40. Check whether four points make a parallelogram
230
Chapter 40. Check whether four points make a parallelogram
Output:
Source
https://www.geeksforgeeks.org/check-whether-four-points-make-parallelogram/
231
Chapter 41
Check whether given circle resides in boundary maintained by two other circles - Geeks-
forGeeks
Given outer circle radius R and inner circle radius r, making circles from same center and
forming boundary between them. Now, given X,Y co-ordinates which denotes center of new
circle to be formed with radius rad, your task is to check whether the circle with co-ordinate
X,Y as center can fit in the boundary of circles formed or not.
Examples:
Input : R = 8, r = 4
x = 5, y = 3, rad = 1
Output : Fits
Input : R = 8, r = 4
x = 5, y = 3, rad = 3.
Output : Doesn't Fit
232
Chapter 41. Check whether given circle resides in boundary maintained by two other circles
1 – Doesn’t fits
2 – Fits
The idea is to calculate the distance between the center (0, 0) and the co-ordinates of the
circle to be checked. If distance + radius (of the circle to be checked) is less than or equal
to Outer Radius and distance – radius (of the circle to be checked) is greater than or equal
to Radius of Outer circle – Radius Inner circle
It fits.
Here is the implementation :
233
Chapter 41. Check whether given circle resides in boundary maintained by two other circles
C++
Java
234
Chapter 41. Check whether given circle resides in boundary maintained by two other circles
// boundary or not
static void fitOrNotFit(int R, int r, int x, int y,
int rad)
{
// Distance from the center
double val = Math.sqrt(Math.pow(x, 2) +
Math.pow(y, 2));
// Checking the corners of circle
if (val + rad <= R && val - rad >= R - r)
System.out.println("Fits");
else
System.out.println("Doesn't Fit");
}
// driver program
public static void main (String[] args)
{
// Radius of outer circle and inner circle
// respectively
int R = 8, r = 4;
// Co-ordinates and radius of the circle
// to be checked
int x = 5, y = 3, rad = 3;
fitOrNotFit(R, r, x, y, rad);
}
}
/* This Code is contributed by Kriti Shukla */
Python3
235
Chapter 41. Check whether given circle resides in boundary maintained by two other circles
# Checking the corners of circle
if (val + rad <= R and val - rad >= R - r) :
print("Fits\n")
else:
print("Doesn't Fit")
# driver program
# Radius of outer circle and inner circle
# respectively
R = 8
r = 4
# Co-ordinates and radius of the circle
# to be checked
x = 5
y = 3
rad = 3
fitOrNotFit(R, r, x, y, rad)
# This code is contributed by
# Smitha Dinesh Semwal
C#
236
Chapter 41. Check whether given circle resides in boundary maintained by two other circles
Console.WriteLine("Doesn't Fit");
}
// Driver program
public static void Main ()
{
// Radius of outer circle and inner circle
// respectively
int R = 8, r = 4;
// Co-ordinates and radius of the circle
// to be checked
int x = 5, y = 3, rad = 3;
fitOrNotFit(R, r, x, y, rad);
}
}
// This Code is contributed by Anant Agarwal.
PHP
<?php
// PHP program to check whether
// circle with given co-ordinates
// reside within the boundary
// of outer circle and inner circle
// function to check if given
// circle fit in boundary or not
function fitOrNotFit($R, $r, $x, $y,
$rad)
{
// Distance from the center
$val = sqrt(pow($x, 2) + pow($y, 2));
// Checking the corners of circle
if ($val + $rad <= $R && $val -
$rad >= $R - $r)
echo"Fits\n";
else
echo "Doesn't Fit\n";
}
// Driver Code
// Radius of outer circle and
// inner circle respectively
237
Chapter 41. Check whether given circle resides in boundary maintained by two other circles
$R = 8; $r = 4;
// Co-ordinates and radius of
// the circle to be checked
$x = 5; $y = 3; $rad = 3;
fitOrNotFit($R, $r, $x, $y, $rad);
// This Code is contributed by vt_m.
?>
Output:
Doesn't Fit
Improved By : vt_m
Source
https://www.geeksforgeeks.org/check-whether-given-circle-reside-boundary-maintained-outer-circle-inner-circle/
238
Chapter 42
Input : a = 7, b = 10, c = 5
Output : Valid
Input : a = 1 b = 10 c = 12
Output : Invalid
Approach: A triangle is valid if sum of its two sides is greater than the third side. If three
sides are a, b and c, then three conditions should be met.
1.a + b > c
2.a + c > b
3.b + c > a
239
Chapter 42. Check whether triangle is valid or not if sides are given
C++
240
Chapter 42. Check whether triangle is valid or not if sides are given
Java
Python3
241
Chapter 42. Check whether triangle is valid or not if sides are given
return False
else:
return True
# driver code
a = 7
b = 10
c = 5
if checkValidity(a, b, c):
print("Valid")
else:
print("Invalid")
C#
// C# program to check
// validity of any triangle
using System;
class GFG {
// Function to calculate for validity
public static int checkValidity(int a, int b,
int c)
{
// check condition
if (a + b <= c || a + c <= b ||
b + c <= a)
return 0;
else
return 1;
}
// Driver code
public static void Main()
{
int a = 7, b = 10, c = 5;
// function calling and print output
if ((checkValidity(a, b, c)) == 1)
Console.Write("Valid");
else
Console.Write("Invalid");
}
}
242
Chapter 42. Check whether triangle is valid or not if sides are given
PHP
<?php
// PHP program to check if three
// sides form a triangle or not
// function to check if three sider
// form a triangle or not
function checkValidity($a, $b, $c)
{
// check condition
if ($a + $b <= $c ||
$a + $c <= $b ||
$b + $c <= $a)
return false;
else
return true;
}
// Driver Code
$a = 7;
$b = 10;
$c = 5;
if (checkValidity($a, $b, $c))
echo "Valid";
else
echo "Invalid";
// This code is contributed by nitin mittal.
?>
Output :
Valid
Source
https://www.geeksforgeeks.org/check-whether-triangle-valid-not-sides-given/
243
Chapter 43
Input : r = 5.
Output : 12
Below are lattice points on a circle with
radius 5 and origin as (0, 0).
(0,5), (0,-5), (5,0), (-5,0),
(3,4), (-3,4), (-3,-4), (3,-4),
(4,3), (-4,3), (-4,-3), (4,-3).
are 12 lattice point.
To find lattice points, we basically need to find values of (x, y) which satisfy the equation
x2 + y2 = r2 .
For any value of (x, y) that satisfies the above equation we actually have total 4 different
combination which that satisfy the equation. For example if r = 5 and (3, 4) is a pair which
satisfies the equation, there are actually 4 combinations (3, 4) , (-3,4) , (-3,-4) , (3,-4). There
is an exception though, in case of (0, r) or (r, 0) there are actually 2 points as there is no
negative 0.
244
Chapter 43. Circle and Lattice Points
CPP
Java
245
Chapter 43. Circle and Lattice Points
Python3
246
Chapter 43. Circle and Lattice Points
import math
# Function to count Lattice
# podefs on a circle
def countLattice(r):
if (r <= 0):
return 0
# Initialize result as 4 for (r, 0), (-r. 0),
# (0, r) and (0, -r)
result = 4
# Check every value that can be potential x
for x in range(1, r):
# Find a potential y
ySquare = r*r - x*x
y = int(math.sqrt(ySquare))
# checking whether square root is an defeger
# or not. Count increments by 4 for four
# different quadrant values
if (y*y == ySquare):
result += 4
return result
# Driver program
r = 5
print(countLattice(r))
# This code is contributed by
# Smitha Dinesh Semwal
C#
247
Chapter 43. Circle and Lattice Points
{
if (r <= 0)
return 0;
// Initialize result as 4
// for (r, 0), (-r. 0),
// (0, r) and (0, -r)
int result = 4;
// Check every value that
// can be potential x
for (int x = 1; x < r; x++)
{
// Find a potential y
int ySquare = r*r - x*x;
int y = (int)Math.Sqrt(ySquare);
// checking whether square root
// is an integer or not. Count
// increments by 4 for four
// different quadrant values
if (y*y == ySquare)
result += 4;
}
return result;
}
// Driver code
public static void Main()
{
int r = 5;
Console.Write(countLattice(r));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find countLattice
// points on a circle
// Function to count Lattice
// points on a circle
248
Chapter 43. Circle and Lattice Points
function countLattice($r)
{
if ($r <= 0)
return 0;
// Initialize result as 4
// for (r, 0), (-r. 0),
// (0, r) and (0, -r)
$result = 4;
// Check every value that
// can be potential x
for ($x = 1; $x < $r; $x++)
{
// Find a potential y
$ySquare = $r * $r - $x * $x;
$y = ceil(sqrt($ySquare));
// checking whether square
// root is an integer
// or not. Count increments
// by 4 for four different
// quadrant values
if ($y * $y == $ySquare)
$result += 4;
}
return $result;
}
// Driver Code
$r = 5;
echo countLattice($r);
// This code is contributed by nitin mittal
?>
Output:
12
Reference:
http://mathworld.wolfram.com/CircleLatticePoints.html
Improved By : nitin mittal
249
Chapter 43. Circle and Lattice Points
Source
https://www.geeksforgeeks.org/circle-lattice-points/
250
Chapter 44
Classify a triangle
We can solve this problem by first calculating the side length and then classifying on com-
paring of side lengths. Classification by sides is simple, if all sides are equal, triangle will
be equilateral, if any two sides are equal triangle will be Isosceles otherwise it will be
Scalene.
Now angle can be classified by Pythagoras theorem, if sum of square of two sides is equal to
square of third side, triangle will be right angle, if less triangle will be acute angle else
it will be obtuse angle triangle.
Below is written simple code for classification of triangle :
251
Chapter 44. Classify a triangle
};
// Utility method to return square of x
int square(int x)
{
return x * x;
}
// Utility method to sort a, b, c; after this
// method a <= b <= c
void order(int &a, int &b, int &c)
{
int copy[3];
copy[0] = a;
copy[1] = b;
copy[2] = c;
sort(copy, copy + 3);
a = copy[0];
b = copy[1];
c = copy[2];
}
// Utility method to return Square of distance
// between two points
int euclidDistSquare(point p1, point p2)
{
return square(p1.x - p2.x) + square(p1.y - p2.y);
}
// Method to classify side
string getSideClassification(int a, int b, int c)
{
// if all sides are equal
if (a == b && b == c)
return "Equilateral";
// if any two sides are equal
else if (a == b || b == c)
return "Isosceles";
else
return "Scalene";
}
// Method to classify angle
string getAngleClassification(int a, int b, int c)
{
// If addition of sum of square of two side
252
Chapter 44. Classify a triangle
Output:
253
Chapter 44. Classify a triangle
Source
https://www.geeksforgeeks.org/classify-a-triangle/
254
Chapter 45
The Brute force solution is O(n^2), compute the distance between each pair and return the
smallest. We can calculate the smallest distance in O(nLogn) time using Divide and Conquer
strategy. In this post, a O(n x (Logn)^2) approach is discussed. We will be discussing a
O(nLogn) approach in a separate post.
Algorithm
Following are the detailed steps of a O(n (Logn)^2) algortihm.
Input: An array of n points P[]
Output: The smallest distance between two points in the given array.
As a pre-processing step, input array is sorted according to x coordinates.
1) Find the middle point in the sorted array, we can take P[n/2] as middle point.
2) Divide the given array in two halves. The first subarray contains points from P[0] to
P[n/2]. The second subarray contains points from P[n/2+1] to P[n-1].
3) Recursively find the smallest distances in both subarrays. Let the distances be dl and
dr. Find the minimum of dl and dr. Let the minimum be d.
255
Chapter 45. Closest Pair of Points using Divide and Conquer algorithm
4) From above 3 steps, we have an upper bound d of minimum distance. Now we need to
consider the pairs such that one point in pair is from left half and other is from right half.
Consider the vertical line passing through passing through P[n/2] and find all points whose
x coordinate is closer than d to the middle vertical line. Build an array strip[] of all such
points.
256
Chapter 45. Closest Pair of Points using Divide and Conquer algorithm
5) Sort the array strip[] according to y coordinates. This step is O(nLogn). It can be
optimized to O(n) by recursively sorting and merging.
6) Find the smallest distance in strip[]. This is tricky. From first look, it seems to be a
O(n^2) step, but it is actually O(n). It can be proved geometrically that for every point in
strip, we only need to check at most 7 points after it (note that strip is sorted according to
Y coordinate). See thisfor more analysis.
7) Finally return the minimum of d and distance calculated in above step (step 6)
Implementation
Following is C/C++ implementation of the above algorithm.
// A divide and conquer program in C/C++ to find the smallest distance from a
// given set of points.
#include <stdio.h>
257
Chapter 45. Closest Pair of Points using Divide and Conquer algorithm
#include <float.h>
#include <stdlib.h>
#include <math.h>
// A structure to represent a Point in 2D plane
struct Point
{
int x, y;
};
/* Following two functions are needed for library function qsort().
Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
// Needed to sort array of points according to X coordinate
int compareX(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->x - p2->x);
}
// Needed to sort array of points according to Y coordinate
int compareY(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->y - p2->y);
}
// A utility function to find the distance between two points
float dist(Point p1, Point p2)
{
return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y)
);
}
// A Brute Force method to return the smallest distance between two points
// in P[] of size n
float bruteForce(Point P[], int n)
{
float min = FLT_MAX;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}
// A utility function to find minimum of two float values
float min(float x, float y)
258
Chapter 45. Closest Pair of Points using Divide and Conquer algorithm
{
return (x < y)? x : y;
}
// A utility function to find the distance beween the closest points of
// strip of given size. All points in strip[] are sorted accordint to
// y coordinate. They all have an upper bound on minimum distance as d.
// Note that this method seems to be a O(n^2) method, but it's a O(n)
// method as the inner loop runs at most 6 times
float stripClosest(Point strip[], int size, float d)
{
float min = d; // Initialize the minimum distance as d
qsort(strip, size, sizeof(Point), compareY);
// Pick all points one by one and try the next points till the difference
// between y coordinates is smaller than d.
// This is a proven fact that this loop runs at most 6 times
for (int i = 0; i < size; ++i)
for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
if (dist(strip[i],strip[j]) < min)
min = dist(strip[i], strip[j]);
return min;
}
// A recursive function to find the smallest distance. The array P contains
// all points sorted according to x coordinate
float closestUtil(Point P[], int n)
{
// If there are 2 or 3 points, then use brute force
if (n <= 3)
return bruteForce(P, n);
// Find the middle point
int mid = n/2;
Point midPoint = P[mid];
// Consider the vertical line passing through the middle point
// calculate the smallest distance dl on left of middle point and
// dr on right side
float dl = closestUtil(P, mid);
float dr = closestUtil(P + mid, n-mid);
// Find the smaller of two distances
float d = min(dl, dr);
259
Chapter 45. Closest Pair of Points using Divide and Conquer algorithm
// Build an array strip[] that contains points close (closer than d)
// to the line passing through the middle point
Point strip[n];
int j = 0;
for (int i = 0; i < n; i++)
if (abs(P[i].x - midPoint.x) < d)
strip[j] = P[i], j++;
// Find the closest points in strip. Return the minimum of d and closest
// distance is strip[]
return min(d, stripClosest(strip, j, d) );
}
// The main functin that finds the smallest distance
// This method mainly uses closestUtil()
float closest(Point P[], int n)
{
qsort(P, n, sizeof(Point), compareX);
// Use recursive function closestUtil() to find the smallest distance
return closestUtil(P, n);
}
// Driver program to test above functions
int main()
{
Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
int n = sizeof(P) / sizeof(P[0]);
printf("The smallest distance is %f ", closest(P, n));
return 0;
}
Output:
Time Complexity Let Time complexity of above algorithm be T(n). Let us assume that
we use a O(nLogn) sorting algorithm. The above algorithm divides all points in two sets
and recursively calls for two sets. After dividing, it finds the strip in O(n) time, sorts the
strip in O(nLogn) time and finally finds the closest points in strip in O(n) time. So T(n)
can expressed as follows
T(n) = 2T(n/2) + O(n) + O(nLogn) + O(n)
T(n) = 2T(n/2) + O(nLogn)
T(n) = T(n x Logn x Logn)
Notes
1) Time complexity can be improved to O(nLogn) by optimizing step 5 of the above algo-
rithm. We will soon be discussing the optimized solution in a separate post.
260
Chapter 45. Closest Pair of Points using Divide and Conquer algorithm
2) The code finds smallest distance. It can be easily modified to find the points with small-
est distance.
3) The code uses quick sort which can be O(n^2) in worst case. To have the upper bound
as O(n (Logn)^2), a O(nLogn) sorting algorithm like merge sort or heap sort can be used
References:
http://www.cs.umd.edu/class/fall2013/cmsc451/Lects/lect10.pdf
http://www.youtube.com/watch?v=vS4Zn1a9KUc
http://www.youtube.com/watch?v=T3T7T8Ym20M
http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
Source
https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/
261
Chapter 46
We have discussed a divide and conquer solution for this problem. The time complexity of
the implementation provided in the previous post is O(n (Logn)^2). In this post, we discuss
an implementation with time complexity as O(nLogn).
Following is a recap of the algorithm discussed in the previous post.
1) We sort all points according to x coordinates.
2) Divide all points in two halves.
3) Recursively find the smallest distances in both subarrays.
4) Take the minimum of two smallest distances. Let the minimum be d.
5) Create an array strip[] that stores all points which are at most d distance away from the
middle line dividing the two sets.
6) Find the smallest distance in strip[].
7) Return the minimum of d and the smallest distance calculated in above step 6.
The great thing about the above approach is, if the array strip[] is sorted according to y
coordinate, then we can find the smallest distance in strip[] in O(n) time. In the implemen-
tation discussed in previous post, strip[] was explicitly sorted in every recursive call that
made the time complexity O(n (Logn)^2), assuming that the sorting step takes O(nLogn)
262
Chapter 46. Closest Pair of Points | O(nlogn) Implementation
time.
In this post, we discuss an implementation where the time complexity is O(nLogn). The
idea is to presort all points according to y coordinates. Let the sorted array be Py[]. When
we make recursive calls, we need to divide points of Py[] also according to the vertical line.
We can do that by simply processing every point and comparing its x coordinate with x
coordinate of middle line.
Following is C++ implementation of O(nLogn) approach.
// A divide and conquer program in C++ to find the smallest distance from a
// given set of points.
#include <iostream>
#include <float.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
// A structure to represent a Point in 2D plane
struct Point
{
int x, y;
};
/* Following two functions are needed for library function qsort().
Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
// Needed to sort array of points according to X coordinate
int compareX(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->x - p2->x);
}
// Needed to sort array of points according to Y coordinate
int compareY(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->y - p2->y);
}
// A utility function to find the distance between two points
float dist(Point p1, Point p2)
{
return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y)
);
}
263
Chapter 46. Closest Pair of Points | O(nlogn) Implementation
// A Brute Force method to return the smallest distance between two points
// in P[] of size n
float bruteForce(Point P[], int n)
{
float min = FLT_MAX;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}
// A utility function to find minimum of two float values
float min(float x, float y)
{
return (x < y)? x : y;
}
// A utility function to find the distance beween the closest points of
// strip of given size. All points in strip[] are sorted accordint to
// y coordinate. They all have an upper bound on minimum distance as d.
// Note that this method seems to be a O(n^2) method, but it's a O(n)
// method as the inner loop runs at most 6 times
float stripClosest(Point strip[], int size, float d)
{
float min = d; // Initialize the minimum distance as d
// Pick all points one by one and try the next points till the difference
// between y coordinates is smaller than d.
// This is a proven fact that this loop runs at most 6 times
for (int i = 0; i < size; ++i)
for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
if (dist(strip[i],strip[j]) < min)
min = dist(strip[i], strip[j]);
return min;
}
// A recursive function to find the smallest distance. The array Px contains
// all points sorted according to x coordinates and Py contains all points
// sorted according to y coordinates
float closestUtil(Point Px[], Point Py[], int n)
{
// If there are 2 or 3 points, then use brute force
if (n <= 3)
return bruteForce(Px, n);
264
Chapter 46. Closest Pair of Points | O(nlogn) Implementation
265
Chapter 46. Closest Pair of Points | O(nlogn) Implementation
Px[i] = P[i];
Py[i] = P[i];
}
qsort(Px, n, sizeof(Point), compareX);
qsort(Py, n, sizeof(Point), compareY);
// Use recursive function closestUtil() to find the smallest distance
return closestUtil(Px, Py, n);
}
// Driver program to test above functions
int main()
{
Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
int n = sizeof(P) / sizeof(P[0]);
cout << "The smallest distance is " << closest(P, n);
return 0;
}
Output:
Time Complexity:Let Time complexity of above algorithm be T(n). Let us assume that
we use a O(nLogn) sorting algorithm. The above algorithm divides all points in two sets
and recursively calls for two sets. After dividing, it finds the strip in O(n) time. Also, it
takes O(n) time to divide the Py array around the mid vertical line. Finally finds the closest
points in strip in O(n) time. So T(n) can expressed as follows
T(n) = 2T(n/2) + O(n) + O(n) + O(n)
T(n) = 2T(n/2) + O(n)
T(n) = T(nLogn)
References:
http://www.cs.umd.edu/class/fall2013/cmsc451/Lects/lect10.pdf
http://www.youtube.com/watch?v=vS4Zn1a9KUc
http://www.youtube.com/watch?v=T3T7T8Ym20M
http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
Source
https://www.geeksforgeeks.org/closest-pair-of-points-onlogn-implementation/
266
Chapter 47
Input is an array of points specified by their x and y coordinates. The output is the convex
hull of this set of points.
Examples:
Input : points[] = {(0, 0), (0, 4), (-4, 0), (5, 0),
(0, -6), (1, 0)};
Output : (-4, 0), (5, 0), (0, -6), (0, 4)
Pre-requisite:
Tangents between two convex polygons
Algorithm:
Given the set of points for which we have to find the convex hull. Suppose we know the
convex hull of the left half points and the right half points, then the problem now is to
merge these two convex hulls and determine the convex hull for the complete set.
This can be done by finding the upper and lower tangent to the right and left convex hulls.
This is illustrated here Tangents between two convex polygons
267
Chapter 47. Convex Hull using Divide and Conquer Algorithm
Let the left convex hull be a and the right convex hull be b. Then the lower and upper
tangents are named as 1 and 2 respectively, as shown in the figure.
Then the red outline shows the final convex hull.
Now the problem remains, how to find the convex hull for the left and right half. Now
recursion comes into the picture, we divide the set of points until the number of points in
the set is very small, say 5, and we can find the convex hull for these points by the brute
algorithm. The merging of these halves would result in the convex hull for the complete set
of points.
Note:
We have used the brute algorithm to find the convex hull for a small number of points and
it has a time complexity of . But some people suggest the following, the convex
hull for 3 or fewer points is the complete set of points. This is correct but the problem
comes when we try to merge a left convex hull of 2 points and right convex hull of 3 points,
then the program gets trapped in an infinite loop in some special cases. So, to get rid of
this problem I directly found the convex hull for 5 or fewer points by algorithm,
which is somewhat greater but does not affect the overall complexity of the algorithm.
268
Chapter 47. Convex Hull using Divide and Conquer Algorithm
269
Chapter 47. Convex Hull using Divide and Conquer Algorithm
270
Chapter 47. Convex Hull using Divide and Conquer Algorithm
271
Chapter 47. Convex Hull using Divide and Conquer Algorithm
s.insert(a[i]);
s.insert(a[j]);
}
}
}
vector<pair<int, int>>ret;
for (auto e:s)
ret.push_back(e);
// Sorting the points in the anti-clockwise order
mid = {0, 0};
int n = ret.size();
for (int i=0; i<n; i++)
{
mid.first += ret[i].first;
mid.second += ret[i].second;
ret[i].first *= n;
ret[i].second *= n;
}
sort(ret.begin(), ret.end(), compare);
for (int i=0; i<n; i++)
ret[i] = make_pair(ret[i].first/n, ret[i].second/n);
return ret;
}
// Returns the convex hull for the given set of points
vector<pair<int, int>> divide(vector<pair<int, int>> a)
{
// If the number of points is less than 6 then the
// function uses the brute algorithm to find the
// convex hull
if (a.size() <= 5)
return bruteHull(a);
// left contains the left half points
// right contains the right half points
vector<pair<int, int>>left, right;
for (int i=0; i<a.size()/2; i++)
left.push_back(a[i]);
for (int i=a.size()/2; i<a.size(); i++)
right.push_back(a[i]);
// convex hull for the left and right sets
vector<pair<int, int>>left_hull = divide(left);
vector<pair<int, int>>right_hull = divide(right);
272
Chapter 47. Convex Hull using Divide and Conquer Algorithm
Output:
Convex Hull:
-5 -3
-1 -5
1 -4
0 0
-1 1
Time Complexity: The merging of the left and the right convex hulls take O(n) time
and as we are dividing the points into two equal parts, so the time complexity of the above
algorithm is O(n * log n).
Related Articles :
273
Chapter 47. Convex Hull using Divide and Conquer Algorithm
Source
https://www.geeksforgeeks.org/convex-hull-using-divide-and-conquer-algorithm/
274
Chapter 48
275
Chapter 48. Convex Hull | Set 1 (Jarvis’s Algorithm or Wrapping)
…..a) The next point q is the point such that the triplet (p, q, r) is counterclockwise for any
other point r.
…..b) next[p] = q (Store q as next of p in the output convex hull).
…..c) p = q (Set p as q for next iteration).
C++
276
Chapter 48. Convex Hull | Set 1 (Jarvis’s Algorithm or Wrapping)
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
// Prints convex hull of a set of n points.
void convexHull(Point points[], int n)
{
// There must be at least 3 points
if (n < 3) return;
// Initialize Result
vector<Point> hull;
// Find the leftmost point
int l = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[l].x)
l = i;
// Start from leftmost point, keep moving counterclockwise
// until reach the start point again. This loop runs O(h)
// times where h is number of points in result or output.
int p = l, q;
do
{
// Add current point to result
hull.push_back(points[p]);
// Search for a point 'q' such that orientation(p, x,
// q) is counterclockwise for all points 'x'. The idea
// is to keep track of last visited most counterclock-
// wise point in q. If any point 'i' is more counterclock-
// wise than q, then update q.
q = (p+1)%n;
for (int i = 0; i < n; i++)
{
// If i is more counterclockwise than current q, then
// update q
if (orientation(points[p], points[i], points[q]) == 2)
q = i;
}
// Now q is the most counterclockwise with respect to p
// Set p as q for next iteration, so that q is added to
// result 'hull'
p = q;
277
Chapter 48. Convex Hull | Set 1 (Jarvis’s Algorithm or Wrapping)
Java
278
Chapter 48. Convex Hull | Set 1 (Jarvis’s Algorithm or Wrapping)
}
// Prints convex hull of a set of n points.
public static void convexHull(Point points[], int n)
{
// There must be at least 3 points
if (n < 3) return;
// Initialize Result
Vector<Point> hull = new Vector<Point>();
// Find the leftmost point
int l = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[l].x)
l = i;
// Start from leftmost point, keep moving
// counterclockwise until reach the start point
// again. This loop runs O(h) times where h is
// number of points in result or output.
int p = l, q;
do
{
// Add current point to result
hull.add(points[p]);
// Search for a point 'q' such that
// orientation(p, x, q) is counterclockwise
// for all points 'x'. The idea is to keep
// track of last visited most counterclock-
// wise point in q. If any point 'i' is more
// counterclock-wise than q, then update q.
q = (p + 1) % n;
for (int i = 0; i < n; i++)
{
// If i is more counterclockwise than
// current q, then update q
if (orientation(points[p], points[i], points[q])
== 2)
q = i;
}
// Now q is the most counterclockwise with
// respect to p. Set p as q for next iteration,
// so that q is added to result 'hull'
p = q;
279
Chapter 48. Convex Hull | Set 1 (Jarvis’s Algorithm or Wrapping)
} while (p != l); // While we don't come to first
// point
// Print Result
for (Point temp : hull)
System.out.println("(" + temp.x + ", " +
temp.y + ")");
}
/* Driver program to test above function */
public static void main(String[] args)
{
Point points[] = new Point[7];
points[0]=new Point(0, 3);
points[1]=new Point(2, 3);
points[2]=new Point(1, 1);
points[3]=new Point(2, 1);
points[4]=new Point(3, 0);
points[5]=new Point(0, 0);
points[6]=new Point(3, 3);
int n = points.length;
convexHull(points, n);
}
}
// This code is contributed by Arnav Kr. Mandal.
(0, 3)
(0, 0)
(3, 0)
(3, 3)
Time Complexity: For every point on the hull we examine all the other points to determine
the next point. Time complexity is ?(m * n) where n is number of input points and m is
number of output or hull points (m <= n). In worst case, time complexity is O(n 2 ). The
worst case occurs when all the points are on the hull (m = n)
Set 2- Convex Hull (Graham Scan)
Sources:
http://www.cs.uiuc.edu/~jeffe/teaching/373/notes/x05-convexhull.pdf
http://www.dcs.gla.ac.uk/~pat/52233/slides/Hull1x1.pdf
280
Chapter 48. Convex Hull | Set 1 (Jarvis’s Algorithm or Wrapping)
Source
https://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/
281
Chapter 49
282
Chapter 49. Convex Hull | Set 2 (Graham Scan)
2) Consider the remaining n-1 points and sort them by polor angle in counterclockwise order
around points[0]. If polor angle of two points is same, then put the nearest point first.
3 After sorting, check if two or more points have same angle. If two more points have same
angle, then remove all same angle points except the point farthest from P0. Let the size of
new array be m.
4) If m is less than 3, return (Convex Hull not possible)
5) Create an empty stack ‘S’ and push points[0], points[1] and points[2] to S.
6) Process remaining m-3 points one by one. Do following for every point ‘points[i]’
4.1) Keep removing points from stack while orientationof following 3 points is not
counterclockwise (or they don’t make a left turn).
a) Point next to top in stack
b) Point at the top of stack
c) points[i]
4.2) Push points[i] to S
5) Print contents of S
The above algorithm can be divided in two phases.
Phase 1 (Sort points): We first find the bottom-most point. The idea is to pre-process
points be sorting them with respect to the bottom-most point. Once the points are sorted,
they form a simple closed path (See following diagram).
What should be the sorting criteria? computation of actual angles would be inefficient
since trigonometric functions are not simple to evaluate. The idea is to use the orientation
to compare angles without actually computing them (See the compare() function below)
Phase 2 (Accept or Reject Points): Once we have the closed path, the next step is to
traverse the path and remove concave points on this path. How to decide which point to
remove and which to keep? Again, orientationhelps here. The first two points in sorted array
are always part of Convex Hull. For remaining points, we keep track of recent three points,
and find the angle formed by them. Let the three points be prev(p), curr(c) and next(n).
If orientation of these points (considering them in same order) is not counterclockwise, we
discard c, otherwise we keep it. Following diagram shows step by step process of this phase
283
Chapter 49. Convex Hull | Set 2 (Graham Scan)
284
Chapter 49. Convex Hull | Set 2 (Graham Scan)
}
// A utility function to swap two points
int swap(Point &p1, Point &p2)
{
Point temp = p1;
p1 = p2;
p2 = temp;
}
// A utility function to return square of distance
// between p1 and p2
int distSq(Point p1, Point p2)
{
return (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y);
}
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
// A function used by library function qsort() to sort an array of
// points with respect to the first point
int compare(const void *vp1, const void *vp2)
{
Point *p1 = (Point *)vp1;
Point *p2 = (Point *)vp2;
// Find orientation
int o = orientation(p0, *p1, *p2);
if (o == 0)
return (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1;
return (o == 2)? -1: 1;
}
// Prints convex hull of a set of n points.
285
Chapter 49. Convex Hull | Set 2 (Graham Scan)
286
Chapter 49. Convex Hull | Set 2 (Graham Scan)
Output:
(0, 3)
(4, 4)
(3, 1)
(0, 0)
Time Complexity: Let n be the number of input points. The algorithm takes O(nLogn)
time if we use a O(nLogn) sorting algorithm.
The first step (finding the bottom-most point) takes O(n) time. The second step (sorting
287
Chapter 49. Convex Hull | Set 2 (Graham Scan)
points) takes O(nLogn) time. Third step takes O(n) time. In third step, every element is
pushed and popped at most one time. So the sixth step to process points one by one takes
O(n) time, assuming that the stack operations take O(1) time. Overall complexity is O(n)
+ O(nLogn) + O(n) + O(n) which is O(nLogn)
References:
Introduction to Algorithms 3rd Edition by Clifford Stein, Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest
http://www.dcs.gla.ac.uk/~pat/52233/slides/Hull1x1.pdf
Please write comments if you find anything incorrect, or you want to share more information
about the topic discussed above.
Source
https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
288
Chapter 50
For finding the smallest rectangle you may take two of basic approach :
1. Consider origin of coordinate plane as smallest rectangle and then step by step keep
expanding it as per value of coordinates of points if they don’t lie inside the current
rectangle. This concept requires a little of complex logic to find the exact smallest
rectangle.
2. A very simple and efficient logic behind this is to find the smallest as well as largest
x & y coordinates among all given points and then the all possible four combinations
of these values result the four points of required rectangle as {Xmin, Ymin}, {Xmin,
Ymax}, {Xmax, Ymax}, {Xmax, Ymin}.
C++
289
Chapter 50. Coordinates of rectangle with given points lie inside
Java
290
Chapter 50. Coordinates of rectangle with given points lie inside
Python 3
291
Chapter 50. Coordinates of rectangle with given points lie inside
print("{",Xmax,", ",Ymax,"}",sep="" )
print("{",Xmax,", ",Ymin,"}",sep="" )
# driver program
X = [4, 3, 6, 1, -1, 12]
Y = [4, 1, 10, 3, 7, -1]
n = len(X)
printRect(X, Y, n)
# This code is contributed by
# Smitha Dinesh Semwal
C#
292
Chapter 50. Coordinates of rectangle with given points lie inside
PHP
<?php
// PHP Program to find smallest
// rectangle to conquer all points
// function to print coordinate
// of smallest rectangle
function printRect($X, $Y, $n)
{
// find Xmax and Xmin
$Xmax = max($X);
$Xmin = min($X);
// find Ymax and Ymin
$Ymax = max($Y);
$Ymin = min($Y);
// print all four coordinates
echo "{" , $Xmin , ", " , $Ymin , "}","\n";
echo "{" , $Xmin , ", " , $Ymax , "}" ,"\n";
echo "{" , $Xmax , ", " , $Ymax , "}","\n";
echo "{" , $Xmax , ", " , $Ymin , "}" ;
}
// Driver Code
$X = array(4, 3, 6, 1, -1, 12);
$Y = array(4, 1, 10, 3, 7, -1);
$n =count($X);
printRect($X, $Y, $n);
// This code is contributed by anuj_67.
?>
293
Chapter 50. Coordinates of rectangle with given points lie inside
Output:
{-1, -1}
{-1, 10}
{12, 10}
{12, -1}
Source
https://www.geeksforgeeks.org/coordinates-rectangle-given-points-lie-inside/
294
Chapter 51
Output: 6
We can use the Pick’s theorem, which states that the following equation holds true for a
simple Polygon.
Pick's Theeorem:
A = I + (B/2) -1
295
Chapter 51. Count Integral points inside a Triangle
296
Chapter 51. Count Integral points inside a Triangle
297
Chapter 51. Count Integral points inside a Triangle
Output:
Source
https://www.geeksforgeeks.org/count-integral-points-inside-a-triangle/
298
Chapter 52
We can solve above problem by following approach – For each point p, calculate its slope
with other points and use a map to record how many points have same slope, by which we
can find out how many points are on same line with p as their one point. For each point
keep doing the same thing and update the maximum number of point count found so far.
Some things to note in implementation are:
1) if two point are (x1, y1) and (x2, y2) then their slope will be (y2 – y1) / (x2 – x1)
which can be a double value and can cause precision problems. To get rid of the precision
problems, we treat slope as pair ((y2 – y1), (x2 – x1)) instead of ratio and reduce pair by
their gcd before inserting into map. In below code points which are vertical or repeated are
treated separately.
2) If we use unordered_map in c++ or HashMap in Java for storing the slope pair, then
total time complexity of solution will be O(n^2)
299
Chapter 52. Count maximum points on same line
300
Chapter 52. Count maximum points on same line
yDif /= g;
xDif /= g;
// increasing the frequency of current slope
// in map
slopeMap[make_pair(yDif, xDif)]++;
curMax = max(curMax, slopeMap[make_pair(yDif, xDif)]);
}
curMax = max(curMax, verticalPoints);
}
// updating global maximum by current point's maximum
maxPoint = max(maxPoint, curMax + overlapPoints + 1);
// printf("maximum colinear point
// which contains current point
// are : %d\n", curMax + overlapPoints + 1);
slopeMap.clear();
}
return maxPoint;
}
// Driver code
int main()
{
const int N = 6;
int arr[N][2] = {{-1, 1}, {0, 0}, {1, 1}, {2, 2},
{3, 3}, {3, 4}};
vector< pair<int, int> > points;
for (int i = 0; i < N; i++)
points.push_back(make_pair(arr[i][0], arr[i][1]));
cout << maxPointOnSameLine(points) << endl;
return 0;
}
Output:
Improved By : PortgasDAce
301
Chapter 52. Count maximum points on same line
Source
https://www.geeksforgeeks.org/count-maximum-points-on-same-line/
302
Chapter 53
Count of acute, obtuse and right triangles with given sides - GeeksforGeeks
Given an array of n positive distinct integers representing lengths of lines that can form
triangle. The task is to find the number of acute triangles, obtuse triangles, and right
triangles separately that can be formed from the given array.
Examples:
303
Chapter 53. Count of acute, obtuse and right triangles with given sides
304
Chapter 53. Count of acute, obtuse and right triangles with given sides
if (b[i]+b[j]==b[p])
{
// All triangle between j and p are acute
// triangles. So add p - j - 1 in x.
x += max(p - j - 1, 0);
// Increment y by 1.
y++;
// All triangle between q and p are acute
// triangles. So add q - p in z.
z += q - p;
}
// If no right triangle
else
{
// All triangle between j and p are acute
// triangles. So add p - j in x.
x += max(p - j, 0);
// All triangle between q and p are acute
// triangles. So add q - p in z.
z += q - p;
}
}
}
cout << "Acute Triangle: " << x << endl;
cout << "Right Triangle: " << y << endl;
cout << "Obtuse Triangle: " << z << endl;
}
// Driver Code
int main()
{
int arr[] = {2, 3, 9, 10, 12, 15};
int n = sizeof(arr)/sizeof(arr[0]);
findTriangle(arr, n);
return 0;
}
Output:
Acute Triangle: 2
Right Triangle: 1
Obtuse Triangle: 4
305
Chapter 53. Count of acute, obtuse and right triangles with given sides
Source
https://www.geeksforgeeks.org/count-of-acute-obtuse-and-right-triangles-with-given-sides/
306
Chapter 54
Count of different straight lines with total n points with m collinear - GeeksforGeeks
There are ‘n’ points in a plane out of which ‘m points are collinear. How many different
straight lines can form?
Examples:
Input : n = 3, m = 3
Output : 1
We can form only 1 distinct straight line
using 3 collinear points
Input : n = 10, m = 4
Output : 40
307
Chapter 54. Count of different straight lines with total n points with m collinear
Since straight lines formed by these 4 points are sane, straight lines formed by
them will reduce to only one.
Required number of straight lines formed = 10 C2 – 4 C2 + 1 = 45 – 6 + 1 = 40
C++
308
Chapter 54. Count of different straight lines with total n points with m collinear
/* driver function*/
int main()
{
int n = 4, m = 3 ;
cout << count_Straightlines(n, m);
return 0;
}
Java
309
Chapter 54. Count of different straight lines with total n points with m collinear
// Driver function
public static void main(String argc[])
{
int n = 4, m = 3;
System.out.println(count_Straightlines(n, m));
}
// This code is contributed by Sagar Shukla
}
Python
310
Chapter 54. Count of different straight lines with total n points with m collinear
print( count_Straightlines(n, m) );
# This code is contributed by "rishabh_jain".
C#
311
Chapter 54. Count of different straight lines with total n points with m collinear
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to count number of straight lines
// with n total points, out of which m are
// collinear.
// Returns value of binomial coefficient
function nCk($n, $k)
{
$C = array_fill(0, $k + 1, NULL);
$C[0] = 1; // nC0 is 1
for ($i = 1; $i <= $n; $i++)
{
// Compute next row of pascal triangle
// using the previous row
for ($j = min($i, $k); $j > 0; $j--)
$C[$j] = $C[$j] + $C[$j-1];
}
return $C[$k];
}
// function to calculate
// number of straight lines
// can be formed
function count_Straightlines($n, $m)
{
return (nCk($n, 2) - nCk($m, 2) + 1);
}
// Driver Code
$n = 4;
$m = 3;
echo(count_Straightlines($n, $m));
312
Chapter 54. Count of different straight lines with total n points with m collinear
Output:
Source
https://www.geeksforgeeks.org/count-different-straight-lines-total-n-points-m-collinear/
313
Chapter 55
Count of obtuse angles in a circle with ’k’ equidistant points between 2 given points -
GeeksforGeeks
A circle is given with k equidistant points on its circumference. 2 points A and B are given
in the circle. Find the count of all obtuse angles (angles larger than 90 degree) formed from
/_ACB, where C can be any point in circle other than A or B.
Note :
A and B are not equal.
A < B.
Points are between 1 and K(both inclusive).
314
Chapter 55. Count of obtuse angles in a circle with ‘k’ equidistant points between 2 given
points
Examples :
Input : K = 6, A = 1, B = 3.
Output : 1
Explanation : In the circle with 6
equidistant points, when C = 2 i.e.
/_123, we get obtuse angle.
Input : K = 6, A = 1, B = 4.
Output : 0
Explanation : In this circle, there
is no such C that form an obtuse angle.
It can be observed that if A and B have equal elements in between them, there can’t be any
C such that ACB is obtuse. Also, the number of possible obtuse angles are the smaller arc
between A and B.
Below is the implementation :
C++
315
Chapter 55. Count of obtuse angles in a circle with ‘k’ equidistant points between 2 given
points
Java
316
Chapter 55. Count of obtuse angles in a circle with ‘k’ equidistant points between 2 given
points
}
// Driver Program to test above function
public static void main(String arg[])
{
int k = 6, a = 1, b = 3;
System.out.print(countObtuseAngles(a, b, k));
}
}
// This code is contributed by Anant Agarwal.
Python
C#
317
Chapter 55. Count of obtuse angles in a circle with ‘k’ equidistant points between 2 given
points
PHP
<?php
// PHP program to count number
// of obtuse angles for given
// two points.
function countObtuseAngles($a, $b, $k)
{
// There are two arcs connecting a
// and b. Let us count points on
// both arcs.
$c1 = ($b - $a) - 1;
$c2 = ($k - $b) + ($a - 1);
318
Chapter 55. Count of obtuse angles in a circle with ‘k’ equidistant points between 2 given
points
// Both arcs have same number of
// points
if ($c1 == $c2)
return 0;
// Points on smaller arc is answer
return min($c1, $c2);
}
// Driver code
$k = 6; $a = 1; $b = 3;
echo countObtuseAngles($a, $b, $k);
// This code is contributed by aj_36
?>
Output :
Source
https://www.geeksforgeeks.org/count-obtuse-angles-circle-k-equidistant-points-2-given-points/
319
Chapter 56
Count of parallelograms in a
plane
Input : points[] = {(0, 0), (0, 2), (2, 2), (4, 2),
(1, 4), (3, 4)}
Output : 2
Two Parallelograms are possible by choosing above
given point as vertices, which are shown in below
diagram.
We can solve this problem by using a special property of parallelograms that diagonals of a
parallelogram intersect each other in the middle. So if we get such a middle point which is
middle point of more than one line segment, then we can conclude that a parallelogram exists,
more accurately if a middle point occurs x times, then diagonals of possible parallelograms
can be chosen in x C2 ways, i.e. there will be x*(x-1)/2 parallelograms corresponding to this
particular middle point with a frequency x. So we iterate over all pair of points and we
calculate their middle point and increase frequency of middle point by 1. At the end, we
count number of parallelograms according to the frequency of each distinct middle point as
explained above. As we just need frequency of middle point, division by 2 is ignored while
calculating middle point for simplicity.
320
Chapter 56. Count of parallelograms in a plane
#include <bits/stdc++.h>
using namespace std;
// Returns count of Parallelograms possible
// from given points
int countOfParallelograms(int x[], int y[], int N)
{
// Map to store frequency of mid points
map<pair<int, int>, int> cnt;
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 midX = x[i] + x[j];
int midY = y[i] + y[j];
// increase the frequency of mid point
cnt[make_pair(midX, midY)]++;
}
}
// Iterating through all mid points
int res = 0;
for (auto it = cnt.begin(); it != cnt.end(); it++)
{
int freq = it->second;
// Increase the count of Parallelograms by
// applying function on frequency of mid point
res += freq*(freq - 1)/2
}
return res;
}
// Driver code to test above methods
int main()
{
int x[] = {0, 0, 2, 4, 1, 3};
int y[] = {0, 2, 2, 2, 4, 4};
int N = sizeof(x) / sizeof(int);
cout << countOfParallelograms(x, y, N) << endl;
return 0;
}
321
Chapter 56. Count of parallelograms in a plane
Output:
Source
https://www.geeksforgeeks.org/count-parallelograms-plane/
322
Chapter 57
Input : N = 2
Output : 2
Explanation: If points are numbered 1 to 4 in
clockwise direction, then different ways to
draw chords are:
{(1-2), (3-4)} and {(1-4), (2-3)}
Input : N = 1
Output : 1
Explanation: Draw a chord between points 1 and 2.
If we draw a chord between any two points, can you observe the current set of points
getting broken into two smaller sets S_1 and S_2. If we draw a chord from a point in S_1
to a point in S_2, it will surely intersect the chord we’ve just drawn.
So, we can arrive at a recurrence that Ways(n) = sum[i = 0 to n-1] { Ways(i)*Ways(n-i-1)
}.
Here we iterate over i, assuming that size of one of the sets is i and size of another set
automatically is (n-i-1) since we’ve already used a pair of points and i pair of points in one set.
C++
323
Chapter 57. Count ways to divide circle using N non-intersecting chords
Java
324
Chapter 57. Count ways to divide circle using N non-intersecting chords
class GFG {
static int chordCnt(int A)
{
// n = no of points required
int n = 2 * A;
// dp array containing the sum
int[] dpArray = new int[n + 1];
dpArray[0] = 1;
dpArray[2] = 1;
for (int i = 4; i <= n; i += 2) {
for (int j = 0; j < i - 1; j += 2)
{
dpArray[i] += (dpArray[j] *
dpArray[i - 2 - j]);
}
}
// returning the required number
return dpArray[n];
}
public static void main(String[] args)
{
int N;
N = 2;
System.out.println(chordCnt(N));
N = 1;
System.out.println(chordCnt(N));
N = 4;
System.out.println(chordCnt(N));
}
}
// This code is contributed by Gitanjali.
Python 3
325
Chapter 57. Count ways to divide circle using N non-intersecting chords
dpArray[0] = 1
dpArray[2] = 1
for i in range(4, n + 1, 2):
for j in range(0, i-1, 2):
dpArray[i] += (dpArray[j]*dpArray[i-2-j])
# returning the required number
return int(dpArray[n])
# driver code
N = 2
print(chordCnt( N))
N = 1
print(chordCnt( N))
N = 4
print(chordCnt( N))
C#
326
Chapter 57. Count ways to divide circle using N non-intersecting chords
Output:
2
1
14
Source
https://www.geeksforgeeks.org/count-ways-divide-circle-using-n-non-intersecting-chords/
327
Chapter 58
328
Chapter 58. Deleting points from Convex Hull
329
Chapter 58. Deleting points from Convex Hull
330
Chapter 58. Deleting points from Convex Hull
}
int lowera = inda, lowerb = indb;
vector<pair<int, int> > ret;
//ret contains the convex hull after merging the two convex hulls
//with the points sorted in anti-clockwise order
int ind = uppera;
ret.push_back(a[uppera]);
while (ind != lowera)
{
ind = (ind+1)%n1;
ret.push_back(a[ind]);
}
ind = lowerb;
ret.push_back(b[lowerb]);
while (ind != upperb)
{
ind = (ind+1)%n2;
ret.push_back(b[ind]);
}
return ret;
}
// Brute force algorithm to find convex hull for a set
// of less than 6 points
vector<pair<int, int> > bruteHull(vector<pair<int, int> > a)
{
// Take any pair of points from the set and check
// whether it is the edge of the convex hull or not.
// if all the remaining points are on the same side
// of the line then the line is the edge of convex
// hull otherwise not
set<pair<int, int> >s;
for (int i=0; i<a.size(); i++)
{
for (int j=i+1; j<a.size(); j++)
{
int x1 = a[i].first, x2 = a[j].first;
int y1 = a[i].second, y2 = a[j].second;
int a1 = y1-y2;
int b1 = x2-x1;
int c1 = x1*y2-y1*x2;
int pos = 0, neg = 0;
331
Chapter 58. Deleting points from Convex Hull
332
Chapter 58. Deleting points from Convex Hull
333
Chapter 58. Deleting points from Convex Hull
int main()
{
vector<pair<int, int> > a;
a.push_back(make_pair(0, 0));
a.push_back(make_pair(1, -4));
a.push_back(make_pair(-1, -5));
a.push_back(make_pair(-5, -3));
a.push_back(make_pair(-3, -1));
a.push_back(make_pair(-1, -3));
a.push_back(make_pair(-2, -2));
a.push_back(make_pair(-1, -1));
a.push_back(make_pair(-2, -1));
a.push_back(make_pair(-1, 1));
int n = a.size();
// sorting the set of points according
// to the x-coordinate
sort(a.begin(), a.end());
vector<pair<int, int> >hull = findHull(a);
cout << "Convex hull:\n";
for (auto e : hull)
cout << e.first << " "
<< e.second << endl;
pair<int, int> p = make_pair(-5, -3);
removePoint(a, hull, p);
cout << "\nModified Convex Hull:\n";
for (auto e:hull)
cout << e.first << " "
<< e.second << endl;
return 0;
}
Output:
convex hull:
-3 0
-1 -9
2 -6
5 3
2 5
Time Complexity:
334
Chapter 58. Deleting points from Convex Hull
It is simple to see that the maximum time taken per query is the time taken to construct
the convex hull which is O(n*logn). So, the overall complexity is O(q*n*logn), where q is
the number of points to be deleted.
Source
https://www.geeksforgeeks.org/deleting-points-convex-hull/
335
Chapter 59
The point might lie behind the line segment, in that case we assume imaginary line by
extending the line segment and determine the direction of point.
336
Chapter 59. Direction of a Point from a Line Segment
* There are only three cases, either the point is on left side, or right side or on the line
segment itself.
This is a very fundamental Problem and is commonly encountered for directions in online
map,
Example : Suppose a user A has to go to Point C in the following map, the user first
reaches point B but after that how does user A know that whether he has to make a right
turn or left turn.
Knowing the direction of a point from a line segment also acts a building block to solve
more complicated problem such as :
Line segment Intersection : finding if two line segment intersect
337
Chapter 59. Direction of a Point from a Line Segment
Right Direction
Source
https://www.geeksforgeeks.org/direction-point-line-segment/
338
Chapter 60
339
Chapter 60. Distance between a point and a Plane in 3 D
340
Chapter 60. Distance between a point and a Plane in 3 D
Examples :
Approach: The perpendicular distance (i.e shortest distance) from a given point to a Plane
is the perpendicular distance from that point to the given plane. Let the co-ordinate of the
given point be (x1, y1, z1)
and equation of the plane be given by the equation a * x + b * y + c * z + d = 0, where a,
b and c are real constants.
The formula for distance between a point and Plane in 3-D is given by:
341
Chapter 60. Distance between a point and a Plane in 3 D
float d = 8;
// Function call
shortest_distance(x1, y1, z1, a, b, c, d);
}
// This code is contributed
// by Amber_Saxena.
Java
342
Chapter 60. Distance between a point and a Plane in 3 D
}
// This code is contributed
// by Amber_Saxena.
Python
C#
// C# program to find the
// Perpendicular(shortest)
// distance between a point
// and a Plane in 3 D.
using System;
class GFG
{
// Function to find distance
static void shortest_distance(float x1, float y1,
float z1, float a,
float b, float c,
float d)
{
343
Chapter 60. Distance between a point and a Plane in 3 D
d = Math.Abs((a * x1 + b *
y1 + c * z1 + d));
float e = (float)Math.Sqrt(a * a + b *
b + c * c);
Console.Write(“Perpendicular distance ” +
“is ” + d / e);
}
// Driver code
public static void Main()
{
float x1 = 4;
float y1 = -4;
float z1 = 3;
float a = 2;
float b = -2;
float c = 5;
float d = 8;
// Function call
shortest_distance(x1, y1, z1,
a, b, c, d);
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program to find the
// Perpendicular(shortest)
// distance between a point
// and a Plane in 3 D.
// Function to find distance
function shortest_distance($x1, $y1, $z1,
$a, $b, $c, $d)
{
$d = abs(($a * $x1 + $b * $y1 +
$c * $z1 + $d));
$e = sqrt($a * $a + $b *
$b + $c * $c);
echo "Perpendicular distance is ". $d / $e;
}
// Driver Code
$x1 = 4;
$y1 = -4;
344
Chapter 60. Distance between a point and a Plane in 3 D
$z1 = 3;
$a = 2;
$b = -2;
$c = 5;
$d = 8;
// function call
shortest_distance($x1, $y1, $z1,
$a, $b, $c, $d);
// This code is contributed
// by Amber_Saxena.
?>
Output:
Source
https://www.geeksforgeeks.org/distance-between-a-point-and-a-plane-in-3-d/
345
Chapter 61
346
Chapter 61. Distance between two parallel Planes in 3-D
347
Chapter 61. Distance between two parallel Planes in 3-D
Examples :
=> a1 / a2 = b1 / b2 = c1 / c2
Find a point in any one plane such that the distance from that point to the other plane that
will be the distance between those two planes. The distance can be calculated by using the
formulae:
348
Chapter 61. Distance between two parallel Planes in 3-D
Java