Euclid

Introduction

This problem asks you to provide a computational solution to a well-defined math problem. Before attempting this problem in code, I would recommend doing it by hand so you understand the geometry of the problem. The desired output is the two-dimensional coordinates of two points that satisfy the conditions outlined in the problem.

Algorithm

Store the input point locations as floats or doubles. First, calculate the length of each side of the triangle from the vertices using the distance formula. You will also need lengths AB and AC. Next, calculate the area of the triangle from Heron's formula. Use the specified condition to get the length of AH, which requires a combination of the triangle area calculated previously and some elementary trigonometry. Using the length of AH relative to AC, you can get the x- and y-perturbations of H and G relative to A and B, respectively. Use printf to print the output in the desired format. While the geometry needed to solve the problem takes some thought to generate, the algorithm and implementation are straightforward mathematical calculations. One possible solution is displayed below.

Solution - Java

import java.util.Scanner;
public class Euclid {
	Scanner in  = new Scanner(System.in);
	
	public static void main(String args[]){ new Euclid().go(); }
	
	public void go(){
		while(true){
			// Input ray info
			double ax = in.nextDouble();
			double ay = in.nextDouble();
			double bx = in.nextDouble();
			double by = in.nextDouble();
			double cx = in.nextDouble();
			double cy = in.nextDouble();
			// Input triangle info
			double side1x  = in.nextDouble();
			double side1y  = in.nextDouble();
			double side2x  = in.nextDouble();
			double side2y  = in.nextDouble();
			double side3x  = in.nextDouble();
			double side3y  = in.nextDouble();
			// End-of-test-cases flag
			if (side1x + side1y + side2x +side2y + side3x + side3y == 0.0){
				break;
			}
			// Triangle side lengths
			double side1 = Math.sqrt(Math.pow((side2x - side1x), 2)+ Math.pow((side2y - side1y), 2));
			double side2 = Math.sqrt(Math.pow((side3x - side2x), 2)+ Math.pow((side3y - side2y), 2));
			double side3 = Math.sqrt(Math.pow((side1x - side3x), 2)+ Math.pow((side1y - side3y), 2));
			// Area of triangle
			double s = (side1 + side2 + side3) / 2;
			double area = Math.sqrt(s * (s - side1) * (s - side2) * (s-side3));
			// Length of AH
			double AB = Math.sqrt(Math.pow((bx - ax), 2)+ Math.pow((by - ay), 2));
			double AC = Math.sqrt(Math.pow((cx - ax), 2)+ Math.pow((cy - ay), 2));
			double d = area / AB;
			double cos_theta = ((cx-ax)*(bx-ax)+(cy-ay)*(by-ay)) / (AB * AC);
			double theta = Math.acos(cos_theta);
			double AH = d / Math.sin(theta);
			// Position of H and G
			double hx = ax + (AH / AC)*(cx - ax);
			double hy = ay + (AH / AC)*(cy - ay);
			double gx = bx + (AH / AC)*(cx - ax);
			double gy = by + (AH / AC)*(cy - ay);
			// Print desired output
			System.out.printf("%.3f %.3f %.3f %.3f\n", gx, gy, hx, hy);
		}
	}
}