Find if a point lies inside, outside or on the circumcircle of three points A, B, C
Given four non-collinear points A, B, C, and P. The task is to find whether point P lies inside, outside or on the circumcircle formed by points A, B, and C.
Examples
Input: A = {2, 8}, B = {2, 1}, C = {4, 5}, P = {2, 4};
Output: Point (2, 4) is inside the circumcircle.Input: A = {2, 8}, B = {2, 1}, C = {4, 5}, P = {3, 0};
Output: Point (3, 0) lies outside the circumcircle.
Approach:
- Find the Circumcenter of the triangle formed by the points A, B, and C by the approach discussed in this article.
- After getting the points of the circumcenter in the above step, find the radius of the circumcenter by calculating the distance between the circumcenter and one of the points of A, B, or C using the below formula:
For Point A = (x, y) and Point B = (a, b) The distance between points A and B is given by:- distance = sqrt((x - a)2 + (y - b)2)
- Since we know the radius and circumcenter of the circle and coordinates of point P, find the location of point P by using the approach discussed in this article.
Below is the implementation of the above approach:
C++
// C++ program to find the points // which lies inside, outside or // on the circle #include <bits/stdc++.h> using namespace std; // Structure Pointer to // store x and y coordinates struct point { double x, y; }; // Function to find the line given // two points void lineFromPoints(point P, point Q, double & a, double & b, double & c) { a = Q.y - P.y; b = P.x - Q.x; c = a * (P.x) + b * (P.y); } // Function which converts the // input line to its perpendicular // bisector. It also inputs the // points whose mid-point lies o // on the bisector void perpenBisectorFromLine(point P, point Q, double & a, double & b, double & c) { // Find the mid point point mid_point; // x coordinates mid_point.x = (P.x + Q.x) / 2; // y coordinates mid_point.y = (P.y + Q.y) / 2; // c = -bx + ay c = -b * (mid_point.x) + a * (mid_point.y); // Assign the coefficient of // a and b double temp = a; a = -b; b = temp; } // Returns the intersection point of // two lines double LineInterX( double a1, double b1, double c1, double a2, double b2, double c2) { // Find determinant double determ = a1 * b2 - a2 * b1; double x = (b2 * c1 - b1 * c2); x /= determ; return x; } // Returns the intersection point of // two lines double LineInterY( double a1, double b1, double c1, double a2, double b2, double c2) { // Find determinant double determ = a1 * b2 - a2 * b1; double y = (a1 * c2 - a2 * c1); y /= determ; return y; } // Function to find the point // lies inside, outside or on // the circle void findPosition(point P, point Q, point R, point D) { // Store the coordinates // radius of circumcircle point r; // Line PQ is represented // as ax + by = c double a, b, c; lineFromPoints(P, Q, a, b, c); // Line QR is represented // as ex + fy = g double e, f, g; lineFromPoints(Q, R, e, f, g); // Converting lines PQ and QR // to perpendicular bisectors. // After this, L = ax + by = c // M = ex + fy = g perpenBisectorFromLine(P, Q, a, b, c); perpenBisectorFromLine(Q, R, e, f, g); // The point of intersection // of L and M gives r as the // circumcenter r.x = LineInterX(a, b, c, e, f, g); r.y = LineInterY(a, b, c, e, f, g); // Length of radius double q = (r.x - P.x) * (r.x - P.x) + (r.y - P.y) * (r.y - P.y); // Distance between radius // and the given point D double dis = (r.x - D.x) * (r.x - D.x) + (r.y - D.y) * (r.y - D.y); // Condition for point lies // inside circumcircle if (dis < q) { cout << "Point (" << D.x << ", " << D.y << ") is inside " << "the circumcircle" ; } // Condition for point lies // on circumcircle else if (dis == q) { cout << "Point (" << D.x << ", " << D.y << ") lies on the " << "circumcircle" ; } // Condition for point lies // outside circumcircle else { cout << "Point (" << D.x << ", " << D.y << ") lies outside" << " the circumcircle" ; } } // Driver Code int main() { point A, B, C, D; // Given Points A = { 2, 8 }; B = { 2, 1 }; C = { 4, 5 }; D = { 3, 0 }; // Function call to find // the point lies inside, // outside or on the // circle findPosition(A, B, C, D); return 0; } |
Java
// Java program to find the points // which lies inside, outside or // on the circle class GFG{ // Structure Pointer to // store x and y coordinates static class point { double x, y; public point() { } public point( double x, double y) { this .x = x; this .y = y; } }; // Function to find the line given // two points static void lineFromPoints(point P, point Q, double a, double b, double c) { a = Q.y - P.y; b = P.x - Q.x; c = a * (P.x) + b * (P.y); } // Function which converts the // input line to its perpendicular // bisector. It also inputs the // points whose mid-point lies o // on the bisector static void perpenBisectorFromLine(point P, point Q, double a, double b, double c) { // Find the mid point point mid_point = new point(); // x coordinates mid_point.x = (P.x + Q.x) / 2 ; // y coordinates mid_point.y = (P.y + Q.y) / 2 ; // c = -bx + ay c = -b * (mid_point.x) + a * (mid_point.y); // Assign the coefficient of // a and b double temp = a; a = -b; b = temp; } // Returns the intersection point of // two lines static double LineInterX( double a1, double b1, double c1, double a2, double b2, double c2) { // Find determinant double determ = a1 * b2 - a2 * b1; double x = (b2 * c1 - b1 * c2); x /= determ; return x; } // Returns the intersection point of // two lines static double LineInterY( double a1, double b1, double c1, double a2, double b2, double c2) { // Find determinant double determ = a1 * b2 - a2 * b1; double y = (a1 * c2 - a2 * c1); y /= determ; return y; } // Function to find the point // lies inside, outside or on // the circle static void findPosition(point P, point Q, point R, point D) { // Store the coordinates // radius of circumcircle point r = new point(); // Line PQ is represented // as ax + by = c double a = 0 , b = 0 , c = 0 ; lineFromPoints(P, Q, a, b, c); // Line QR is represented // as ex + fy = g double e = 0 , f = 0 , g = 0 ; lineFromPoints(Q, R, e, f, g); // Converting lines PQ and QR // to perpendicular bisectors. // After this, L = ax + by = c // M = ex + fy = g perpenBisectorFromLine(P, Q, a, b, c); perpenBisectorFromLine(Q, R, e, f, g); // The point of intersection // of L and M gives r as the // circumcenter r.x = LineInterX(a, b, c, e, f, g); r.y = LineInterY(a, b, c, e, f, g); // Length of radius double q = (r.x - P.x) * (r.x - P.x) + (r.y - P.y) * (r.y - P.y); // Distance between radius // and the given point D double dis = (r.x - D.x) * (r.x - D.x) + (r.y - D.y) * (r.y - D.y); // Condition for point lies // inside circumcircle if (dis < q) { System.out.print( "Point (" + D.x+ ", " + D.y+ ") is inside " + "the circumcircle" ); } // Condition for point lies // on circumcircle else if (dis == q) { System.out.print( "Point (" + D.x+ ", " + D.y+ ") lies on the " + "circumcircle" ); } // Condition for point lies // outside circumcircle else { System.out.print( "Point (" + D.x+ ", " + D.y+ ") lies outside" + " the circumcircle" ); } } // Driver Code public static void main(String[] args) { point A, B, C, D; // Given Points A = new point( 2 , 8 ); B = new point( 2 , 1 ); C = new point( 4 , 5 ); D = new point( 3 , 0 ); // Function call to find // the point lies inside, // outside or on the // circle findPosition(A, B, C, D); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to find the points # which lies inside, outside or # on the circle # Function to find the line given # two points def lineFromPoints(P, Q, a, b, c): a = Q[ 1 ] - P[ 1 ] b = P[ 0 ] - Q[ 0 ] c = a * (P[ 0 ]) + b * (P[ 1 ]) return a, b, c # Function which converts the # input line to its perpendicular # bisector. It also inputs the # points whose mid-lies o # on the bisector def perpenBisectorFromLine(P, Q, a, b, c): # Find the mid point mid_point = [ 0 , 0 ] # x coordinates mid_point[ 0 ] = (P[ 0 ] + Q[ 0 ]) / 2 # y coordinates mid_point[ 1 ] = (P[ 1 ] + Q[ 1 ]) / 2 # c = -bx + ay c = ( - b * (mid_point[ 0 ]) + a * (mid_point[ 1 ])) # Assign the coefficient of # a and b temp = a a = - b b = temp return a, b, c # Returns the intersection of # two lines def LineInterX(a1, b1, c1, a2, b2, c2): # Find determinant determ = a1 * b2 - a2 * b1 x = (b2 * c1 - b1 * c2) x / = determ return x # Returns the intersection of # two lines def LineInterY(a1, b1, c1, a2, b2, c2): # Find determinant determ = a1 * b2 - a2 * b1 y = (a1 * c2 - a2 * c1) #print(y) y / = determ return y # Function to find the point # lies inside, outside or on # the circle def findPosition(P, Q, R, D): # Store the coordinates # radius of circumcircle r = [ 0 , 0 ] # Line PQ is represented # as ax + by = c a, b, c = lineFromPoints(P, Q, 0 , 0 , 0 ) # Line QR is represented # as ex + fy = g e, f, g = lineFromPoints(Q, R, 0 , 0 , 0 ) # Converting lines PQ and QR # to perpendicular bisectors. # After this, L = ax + by = c # M = ex + fy = g a, b, c = perpenBisectorFromLine(P, Q, a, b, c) e, f, g = perpenBisectorFromLine(Q, R, e, f, g) # The of intersection # of L and M gives r as the # circumcenter r[ 0 ] = LineInterX(a, b, c, e, f, g) r[ 1 ] = LineInterY(a, b, c, e, f, g) # Length of radius q = ((r[ 0 ] - P[ 0 ]) * (r[ 0 ] - P[ 0 ]) + (r[ 1 ] - P[ 1 ]) * (r[ 1 ] - P[ 1 ])) # Distance between radius # and the given D dis = ((r[ 0 ] - D[ 0 ]) * (r[ 0 ] - D[ 0 ]) + (r[ 1 ] - D[ 1 ]) * (r[ 1 ] - D[ 1 ])) # Condition for lies # inside circumcircle if (dis < q): print ( "Point (" , D[ 0 ], "," , D[ 1 ], ") is inside the circumcircle" ) # Condition for lies # on circumcircle elif (dis = = q): print ( "Point (" , D[ 0 ], "," , D[ 1 ], ") lies on the circumcircle" ) # Condition for lies # outside circumcircle else : print ( "Point (" , D[ 0 ], "," , D[ 1 ], ") lies outside the circumcircle" ) # Driver Code if __name__ = = '__main__' : # A, B, C, D # Given Points A = [ 2 , 8 ] B = [ 2 , 1 ] C = [ 4 , 5 ] D = [ 3 , 0 ] # Function call to find # the lies inside, # outside or on the # circle findPosition(A, B, C, D) # This code is contributed by mohit kumar 29 |
C#
// C# program to find the points // which lies inside, outside or // on the circle using System; class GFG{ // Structure Pointer to // store x and y coordinates class point { public double x, y; public point() { } public point( double x, double y) { this .x = x; this .y = y; } }; // Function to find the line given // two points static void lineFromPoints(point P, point Q, double a, double b, double c) { a = Q.y - P.y; b = P.x - Q.x; c = a * (P.x) + b * (P.y); } // Function which converts the // input line to its perpendicular // bisector. It also inputs the // points whose mid-point lies o // on the bisector static void perpenBisectorFromLine(point P, point Q, double a, double b, double c) { // Find the mid point point mid_point = new point(); // x coordinates mid_point.x = (P.x + Q.x) / 2; // y coordinates mid_point.y = (P.y + Q.y) / 2; // c = -bx + ay c = -b * (mid_point.x) + a * (mid_point.y); // Assign the coefficient of // a and b double temp = a; a = -b; b = temp; } // Returns the intersection point of // two lines static double LineInterX( double a1, double b1, double c1, double a2, double b2, double c2) { // Find determinant double determ = a1 * b2 - a2 * b1; double x = (b2 * c1 - b1 * c2); x /= determ; return x; } // Returns the intersection point of // two lines static double LineInterY( double a1, double b1, double c1, double a2, double b2, double c2) { // Find determinant double determ = a1 * b2 - a2 * b1; double y = (a1 * c2 - a2 * c1); y /= determ; return y; } // Function to find the point // lies inside, outside or on // the circle static void findPosition(point P, point Q, point R, point D) { // Store the coordinates // radius of circumcircle point r = new point(); // Line PQ is represented // as ax + by = c double a = 0, b = 0, c = 0; lineFromPoints(P, Q, a, b, c); // Line QR is represented // as ex + fy = g double e = 0, f = 0, g = 0; lineFromPoints(Q, R, e, f, g); // Converting lines PQ and QR // to perpendicular bisectors. // After this, L = ax + by = c // M = ex + fy = g perpenBisectorFromLine(P, Q, a, b, c); perpenBisectorFromLine(Q, R, e, f, g); // The point of intersection // of L and M gives r as the // circumcenter r.x = LineInterX(a, b, c, e, f, g); r.y = LineInterY(a, b, c, e, f, g); // Length of radius double q = (r.x - P.x) * (r.x - P.x) + (r.y - P.y) * (r.y - P.y); // Distance between radius // and the given point D double dis = (r.x - D.x) * (r.x - D.x) + (r.y - D.y) * (r.y - D.y); // Condition for point lies // inside circumcircle if (dis < q) { Console.Write( "Point (" + D.x+ ", " + D.y+ ") is inside " + "the circumcircle" ); } // Condition for point lies // on circumcircle else if (dis == q) { Console.Write( "Point (" + D.x+ ", " + D.y+ ") lies on the " + "circumcircle" ); } // Condition for point lies // outside circumcircle else { Console.Write( "Point (" + D.x+ ", " + D.y+ ") lies outside" + " the circumcircle" ); } } // Driver Code public static void Main(String[] args) { point A, B, C, D; // Given Points A = new point(2, 8 ); B = new point(2, 1 ); C = new point(4, 5 ); D = new point(3, 0 ); // Function call to find // the point lies inside, // outside or on the // circle findPosition(A, B, C, D); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to find the points // which lies inside, outside or // on the circle // Structure Pointer to // store x and y coordinates class point { constructor(x,y) { this .x = x; this .y = y; } } // Function to find the line given // two points function lineFromPoints(P, Q, a, b, c) { a = Q.y - P.y; b = P.x - Q.x; c = a * (P.x) + b * (P.y); } // Function which converts the // input line to its perpendicular // bisector. It also inputs the // points whose mid-point lies o // on the bisector function perpenBisectorFromLine(P, Q, a, b, c) { // Find the mid point let mid_point = new point(); // x coordinates mid_point.x = (P.x + Q.x) / 2; // y coordinates mid_point.y = (P.y + Q.y) / 2; // c = -bx + ay c = -b * (mid_point.x) + a * (mid_point.y); // Assign the coefficient of // a and b let temp = a; a = -b; b = temp; } // Returns the intersection point of // two lines function LineInterX(a1, b1, c1, a2, b2, c2) { // Find determinant let determ = a1 * b2 - a2 * b1; let x = (b2 * c1 - b1 * c2); x /= determ; return x; } // Returns the intersection point of // two lines function LineInterY(a1, b1, c1, a2, b2, c2) { // Find determinant let determ = a1 * b2 - a2 * b1; let y = (a1 * c2 - a2 * c1); y /= determ; return y; } // Function to find the point // lies inside, outside or on // the circle function findPosition(P, Q, R, D) { // Store the coordinates // radius of circumcircle let r = new point(); // Line PQ is represented // as ax + by = c let a = 0, b = 0, c = 0; lineFromPoints(P, Q, a, b, c); // Line QR is represented // as ex + fy = g let e = 0, f = 0, g = 0; lineFromPoints(Q, R, e, f, g); // Converting lines PQ and QR // to perpendicular bisectors. // After this, L = ax + by = c // M = ex + fy = g perpenBisectorFromLine(P, Q, a, b, c); perpenBisectorFromLine(Q, R, e, f, g); // The point of intersection // of L and M gives r as the // circumcenter r.x = LineInterX(a, b, c, e, f, g); r.y = LineInterY(a, b, c, e, f, g); // Length of radius let q = (r.x - P.x) * (r.x - P.x) + (r.y - P.y) * (r.y - P.y); // Distance between radius // and the given point D let dis = (r.x - D.x) * (r.x - D.x) + (r.y - D.y) * (r.y - D.y); // Condition for point lies // inside circumcircle if (dis < q) { document.write( "Point (" + D.x+ ", " + D.y+ ") is inside " + "the circumcircle" ); } // Condition for point lies // on circumcircle else if (dis == q) { document.write( "Point (" + D.x+ ", " + D.y+ ") lies on the " + "circumcircle" ); } // Condition for point lies // outside circumcircle else { document.write( "Point (" + D.x+ ", " + D.y+ ") lies outside" + " the circumcircle" ); } } // Driver Code let A, B, C, D; // Given Points A = new point(2, 8 ); B = new point(2, 1 ); C = new point(4, 5 ); D = new point(3, 0 ); // Function call to find // the point lies inside, // outside or on the // circle findPosition(A, B, C, D); // This code is contributed by unknown2108 </script> |
Output:
Point (3, 0) lies outside the circumcircle
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us