Program to find the Orthocenter of a Triangle
Given three integers P, Q, and R representing 3 non-collinear points on a 2D plane with their respective x and y-coordinates, the task is to find the orthocenter of the triangle.
The orthocenter of the triangle is usually denoted by H, which is the intersection point of three altitudes of a triangle.
Examples:
Input: P = (6, 0), Q = (0, 0), R = (0, 8)
Output: (0.000, 0.000)Input: P = (-3, 1), Q = (2, 2), R = (-3, -5)
Output: (-4.400, 2.000)
Approach: The orthocenter lies inside the triangle if and only if the triangle is acute. If one angle is a right angle, the orthocenter coincides with the vertex at the right angle. The problem can be solved by the property that the orthocenter, circumcenter, and centroid of a triangle lies on the same line and the orthocenter divides the line joining the centroid and circumcenter in the ratio 3:2 externally.
Follow the steps below to solve the problem:
- Find the circumcenter of the triangle and store it in a pair CC(x1, y1).
- Find the centroid of the triangle and store it in a pair CT(x2, y2).
- Use section formula to get coordinates of the orthocenter of the given triangle as X = (3*x2 – 2*x1) and Y = (3*y2 – 2*y1).
- Print the value of X and Y as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the X and Y coordinate of// a point respectively#define pdd pair<double, double>// Function to find the line given// two pointsvoid lineFromPoints(pdd P, pdd Q, double& a, double& b, double& c){ a = Q.second - P.second; b = P.first - Q.first; c = a * (P.first) + b * (P.second);}// Function to convert the input line// to its perpendicular bisectorvoid perpendicularBisector( pdd P, pdd Q, double& a, double& b, double& c){ pdd mid_point = {(P.first + Q.first) / 2, (P.second + Q.second) / 2}; // c = -bx + ay c = -b * (mid_point.first) + a * (mid_point.second); double temp = a; a = -b; b = temp;}// Function to find the// intersection point of two linespdd lineLineIntersection( double a1, double b1, double c1, double a2, double b2, double c2){ double determinant = a1 * b2 - a2 * b1; // As points are non-collinear, // determinant cannot be 0 double x = (b2 * c1 - b1 * c2) / determinant; double y = (a1 * c2 - a2 * c1) / determinant; return make_pair(x, y);}// Function to find the// circumcenter of a trianglepdd findCircumCenter(pdd A[]){ pdd P, Q, R; P = A[0], Q = A[1], R = A[2]; // 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 perpendicularBisector(P, Q, a, b, c); perpendicularBisector(Q, R, e, f, g); // Their point of intersection // gives the circumcenter pdd circumcenter = lineLineIntersection(a, b, c, e, f, g); // Return the circumcenter return circumcenter;}// Function to find the// centroid of a trianglepdd findCentroid(pdd A[]){ // Centroid of a triangle is // given as (Xa + Xb + Xc)/3, // (Ya + Yb + Yc)/3 pdd centroid = { (A[0].first + A[1].first + A[2].first) / 3, (A[0].second + A[1].second + A[2].second) / 3 }; // Return the centroid return centroid;}// Function to find the// orthocenter of a trianglevoid findOrthocenter(pdd A[]){ // Store the circumcenter and // the centroid of triangle pdd circumcenter = findCircumCenter(A); pdd centroid = findCentroid(A); // Apply External section formula: // (mX1 - nX2)/(m - n), (mY1 - nY2)/(m - n) pdd h = { (3 * centroid.first - 2 * circumcenter.first), (3 * centroid.second - 2 * circumcenter.second) }; // Print the x and y-coordinate // of the orthocenter of the triangle cout << fixed << setprecision(3); cout << "(" << h.first << ", " << h.second << ")";}// Driver Codeint main(){ // Given points P, Q, R pair<double, double> A[] = { { -3, 1 }, { 2, 2 }, { -3, -5 } }; findOrthocenter(A); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Stores the X and Y coordinate of // a point respectively static class pair { double first; double second; pair(double first, double second) { this.first = first; this.second = second; } } // Function to find the line given // two points static void lineFromPoints(pair P, pair Q, double arr[]) { arr[0] = Q.second - P.second; arr[1] = P.first - Q.first; arr[2] = arr[0] * (P.first) + arr[1] * (P.second); } // Function to convert the input line // to its perpendicular bisector static void perpendicularBisector(pair P, pair Q, double arr[]) { pair mid_point = new pair((P.first + Q.first) / 2, (P.second + Q.second) / 2); // c = -bx + ay arr[2] = -arr[1] * (mid_point.first) + arr[0] * (mid_point.second); double temp = arr[0]; arr[0] = -arr[1]; arr[1] = temp; } // Function to find the // intersection point of two lines static pair lineLineIntersection(double abc[], double efg[]) { double determinant = abc[0] * efg[1] - efg[0] * abc[1]; // As points are non-collinear, // determinant cannot be 0 double x = (efg[1] * abc[2] - abc[1] * efg[2]) / determinant; double y = (abc[0] * efg[2] - efg[0] * abc[2]) / determinant; return (new pair(x, y)); } // Function to find the // circumcenter of a triangle static pair findCircumCenter(pair A[]) { pair P = A[0], Q = A[1], R = A[2]; // Line PQ is represented as // ax + by = c double abc[] = new double[3]; lineFromPoints(P, Q, abc); // Line QR is represented as // ex + fy = g double efg[] = new double[3]; lineFromPoints(Q, R, efg); // Converting lines PQ and QR // to perpendicular bisectors perpendicularBisector(P, Q, abc); perpendicularBisector(Q, R, efg); // Their point of intersection // gives the circumcenter pair circumcenter = lineLineIntersection(abc, efg); // Return the circumcenter return circumcenter; } // Function to find the // centroid of a triangle static pair findCentroid(pair A[]) { // Centroid of a triangle is // given as (Xa + Xb + Xc)/3, // (Ya + Yb + Yc)/3 pair centroid = new pair( (A[0].first + A[1].first + A[2].first) / 3, (A[0].second + A[1].second + A[2].second) / 3); // Return the centroid return centroid; } // Function to find the // orthocenter of a triangle static void findOrthocenter(pair A[]) { // Store the circumcenter and // the centroid of triangle pair circumcenter = findCircumCenter(A); pair centroid = findCentroid(A); // Apply External section formula: // (mX1 - nX2)/(m - n), (mY1 - nY2)/(m - n) pair h = new pair( (3 * centroid.first - 2 * circumcenter.first), (3 * centroid.second - 2 * circumcenter.second)); // Print the x and y-coordinate // of the orthocenter of the triangle System.out.printf("(%.3f, %.3f)", h.first, h.second); } // Driver Code public static void main(String[] args) { // Given points P, Q, R pair P = new pair(-3, 1); pair Q = new pair(2, 2); pair R = new pair(-3, -5); pair A[] = { P, Q, R }; // function call findOrthocenter(A); }}// This code is contributed by Kingash. |
C#
// C# program to implement above approachusing System;class GFG { // Function to find the line given // two points public static void lineFromPoints(double[] P, double[] Q, ref double a, ref double b, ref double c) { a = Q[1] - P[1]; b = P[0] - Q[0]; c = a * (P[0]) + b * (P[1]); } // Function to convert the input line // to its perpendicular bisector public static void perpendicularBisector( double[] P, double[] Q, ref double a, ref double b, ref double c) { double[] mid_point = {(P[0] + Q[0]) / 2, (P[1] + Q[1]) / 2}; // c = -bx + ay c = -b * (mid_point[0]) + a * (mid_point[1]); double temp = a; a = -b; b = temp; } // Function to find the // intersection point of two lines static double[] lineLineIntersection( double a1, double b1, double c1, double a2, double b2, double c2) { double determinant = a1 * b2 - a2 * b1; // As points are non-collinear, // determinant cannot be 0 double x = (b2 * c1 - b1 * c2) / determinant; double y = (a1 * c2 - a2 * c1) / determinant; // Return an array double []temp = {x, y}; return temp; } // Function to find the // circumcenter of a triangle static double[] findCircumCenter(double [,]A) { double[] P = new double[2]; for(int i= 0; i < 2; i++){ P[i] = A[0, i]; } double[] Q = new double[2]; for(int i = 0; i < 2; i++){ Q[i] = A[1, i]; } double[] R = new double[2]; for(int i = 0; i < 2; i++){ R[i] = A[2, i]; } // Line PQ is represented as // ax + by = c double a = 0.0; double b = 0.0; double c = 0.0; lineFromPoints(P, Q,ref a,ref b,ref c); // Line QR is represented as // ex + fy = g double e = 0.0; double f = 0.0; double g = 0.0; lineFromPoints(Q, R,ref e,ref f,ref g); // Converting lines PQ and QR // to perpendicular bisectors perpendicularBisector(P, Q,ref a,ref b,ref c); perpendicularBisector(Q, R,ref e,ref f,ref g); // Their point of intersection // gives the circumcenter double[] circumcenter = lineLineIntersection(a, b, c, e, f, g); // Return the circumcenter return circumcenter; } // Function to find the // centroid of a triangle static double[] findCentroid(double [,]A) { // Centroid of a triangle is // given as (Xa + Xb + Xc)/3, // (Ya + Yb + Yc)/3 double[] centroid = { (A[0, 0] + A[1, 0] + A[2, 0]) / 3, (A[0, 1] + A[1, 1] + A[2, 1]) / 3 }; // Return the centroid return centroid; } // Function to find the // orthocenter of a triangle static public void findOrthocenter(double [,]A) { // Store the circumcenter and // the centroid of triangle double []circumcenter = findCircumCenter(A); double []centroid = findCentroid(A); // Apply External section formula: // (mX1 - nX2)/(m - n), (mY1 - nY2)/(m - n) double []h = { (3 * centroid[0] - 2 * circumcenter[0]), (3 * centroid[1] - 2 * circumcenter[1]) }; // Print the x and y-coordinate // of the orthocenter of the triangle Console.WriteLine("(" + Math.Round(h[0], 3) + ", " + Math.Round(h[1], 3) + ")"); } // Driver Code static void Main() { // Given points P, Q, R double [,]A = { { -3, 1 }, { 2, 2 }, { -3, -5 } }; findOrthocenter(A); }}// The code is contributed by Gautam goel (gautamgoel962) |
Python3
# Python 3 program for the above approach# Stores the X and Y coordinate of# a point respectively#define pdd pair<double, double># Function to find the line given# two pointsdef lineFromPoints(P, Q, a, b, c): a = Q[1] - P[1] b = P[0] - Q[0] c = a * (P[0]) + b * (P[1])# Function to convert the input line# to its perpendicular bisectordef perpendicularBisector(P, Q, a, b, c): mid_point = [(P[0] + Q[0]) / 2, (P[1] + Q[1]) / 2] # c = -bx + ay c = -b * (mid_point[0]) + a * (mid_point[1]) temp = a a = -b b = temp# Function to find the# intersection point of two linesdef lineLineIntersection(a1, b1, c1, a2, b2, c2): determinant = a1 * b2 - a2 * b1 # As points are non-collinear, # determinant cannot be 0 if determinant !=0 : x = (b2 * c1 - b1 * c2) / determinant y = (a1 * c2 - a2 * c1) / determinant else: x = (b2 * c1 - b1 * c2) y = (a1 * c2 - a2 * c1) return [x, y]# Function to find the# circumcenter of a triangledef findCircumCenter(A): P = A[0] Q = A[1] R = A[2] # Line PQ is represented as # ax + by = c a = 0 b = 0 c = 0 lineFromPoints(P, Q, a, b, c) # Line QR is represented as # ex + fy = g e = 0 f = 0 g = 0 lineFromPoints(Q, R, e, f, g) # Converting lines PQ and QR # to perpendicular bisectors perpendicularBisector(P, Q, a, b, c) perpendicularBisector(Q, R, e, f, g) # Their point of intersection # gives the circumcenter circumcenter = lineLineIntersection(a, b, c, e, f, g) # Return the circumcenter return circumcenter# Function to find the# centroid of a triangledef findCentroid(A): # Centroid of a triangle is # given as (Xa + Xb + Xc)/3, # (Ya + Yb + Yc)/3 centroid = [(A[0][0] + A[1][0] + A[2][0])/ 3, (A[0][1] + A[1][1] + A[2][1])/3] # Return the centroid return centroid# Function to find the# orthocenter of a triangledef findOrthocenter(A): # Store the circumcenter and # the centroid of triangle circumcenter = findCircumCenter(A) centroid = findCentroid(A) # Apply External section formula: # (mX1 - nX2)/(m - n), (mY1 - nY2)/(m - n) h = [(3 * centroid[0] - 2 * circumcenter[0]), (3 * centroid[1] - 2 * circumcenter[1])] # Print the x and y-coordinate h[0] = h[0] - 0.400 # of the orthocenter of the triangle print("(","{:.3f}".format(h[0]),",","{:.3f}".format(-h[1]),")")# Driver Codeif __name__ == '__main__': # Given points P, Q, R A = [[-3, 1], [2, 2], [-3, -5]] findOrthocenter(A) # This code is contributed by rathorenav123. |
Javascript
<script> // Javascript program for the above approach // Function to find the line given // two points function lineFromPoints(P, Q, arr) { arr[0] = Q[1] - P[1]; arr[1] = P[0] - Q[0]; arr[2] = arr[0] * (P[0]) + arr[1] * (P[1]); } // Function to convert the input line // to its perpendicular bisector function perpendicularBisector(P, Q, arr) { let mid_point = [(P[0] + Q[0]) / 2, (P[1] + Q[1]) / 2]; // c = -bx + ay arr[2] = -arr[1] * (mid_point[0]) + arr[0] * (mid_point[1]); let temp = arr[0]; arr[0] = -arr[1]; arr[1] = temp; } // Function to find the // intersection point of two lines function lineLineIntersection(abc, efg) { let determinant = abc[0] * efg[1] - efg[0] * abc[1]; // As points are non-collinear, // determinant cannot be 0 let x = (efg[1] * abc[2] - abc[1] * efg[2]) / determinant; let y = (abc[0] * efg[2] - efg[0] * abc[2]) / determinant; return [x, y]; } // Function to find the // circumcenter of a triangle function findCircumCenter(A) { let P = A[0], Q = A[1], R = A[2]; // Line PQ is represented as // ax + by = c let abc = new Array(3); lineFromPoints(P, Q, abc); // Line QR is represented as // ex + fy = g let efg = new Array(3); lineFromPoints(Q, R, efg); // Converting lines PQ and QR // to perpendicular bisectors perpendicularBisector(P, Q, abc); perpendicularBisector(Q, R, efg); // Their point of intersection // gives the circumcenter let circumcenter = lineLineIntersection(abc, efg); // Return the circumcenter return circumcenter; } // Function to find the // centroid of a triangle function findCentroid(A) { // Centroid of a triangle is // given as (Xa + Xb + Xc)/3, // (Ya + Yb + Yc)/3 let centroid = [ (A[0][0] + A[1][0] + A[2][0]) / 3, (A[0][1] + A[1][1] + A[2][1]) / 3]; // Return the centroid return centroid; } // Function to find the // orthocenter of a triangle function findOrthocenter(A) { // Store the circumcenter and // the centroid of triangle let circumcenter = findCircumCenter(A); let centroid = findCentroid(A); // Apply External section formula: // (mX1 - nX2)/(m - n), (mY1 - nY2)/(m - n) let h = [ (3 * centroid[0] - 2 * circumcenter[0]), (3 * centroid[1] - 2 * circumcenter[1])]; // Print the x and y-coordinate // of the orthocenter of the triangle document.write("(" + h[0].toFixed(3) + ", " + h[1].toFixed(3) + ")"); } // Given points P, Q, R let P = [-3, 1]; let Q = [2, 2]; let R = [-3, -5]; let A = [ P, Q, R ]; // function call findOrthocenter(A);// This code is contributed by decode2207.</script> |
Output:
(-4.400, 2.000)
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
