Triangle Trilemma

We are asked to write a program to classify triangles, this is an easy one, easy is good because at this time all we need is just one successful solution for the Qualification Round, of course our chances to qualify are higher if we start with the easy problem at the contest.

Click here to download the problem statement.

Step 1: Analyzing the problem

We are given 3 points (six integer values) that may or may not define a triangle.

First, we need to validate if the given points are not collinear, in the following picture we have 3 collinear points, something you have to notice is that for this case the distances (x1-x2) and (x1-x3) are proportional to the (y1-y2) and (y1-y3) respectively.

Collinearity can be represented by the following equation:

(x1 - x2) / (y1 - y2) == (x1 – x3) / (y1 – y3)

But having a difference in the divisor is too risky because in some cases it can give you a division by 0 (zero) exception, so we will rewrite it as:

(x1 - x2) * (y1 – y3) == (x1 – x3) * (y1 - y2)

Collinear means, not a triangle. Notice that this is also validating if two of the points are the same, because in that case the three are collinear.

Now we need to know if the triangle is rectangle, obtuse or acute.

s1 = (x1-x2) *(x1-x2) + (y1-y2)* (y1-y2) // Side 1 ^ 2
s2 = (x1-x3) *(x1-x3) + (y1-y3)* (y1-y3) // Site 2 ^2
s3 = (x3-x2) *(x3-x2) + (y3-y2)* (y3-y2) // Site 3 ^2

Validating if its "right"

s1 == s2 + s3 || s2 == s1 + s3 || s3 == s1 + s2

Validating if its "obtuse"

s1 > s2 + s3 || s2 > s1 + s3 || s3 > s1 + s2

The triangle is "acute" otherwise.

Validating if its "isosceles"

s1 == s2 || s2 == s3 || s1 == s3

Otherwise is "scalene"

Step 2: Start Coding

Here we will focus on coding the logical part, we'll assume that we already have load all the input data in a string[][] array, you can find how we got that array in the previous article "Training for Google Code Jam 2008 with ActionScript3".

Now we need to implement the a function that receives the input data array and returns an output data array, everything we put in this output array will be shown in our output textarea.

// This functions implements the logic of your solution
private function TransformInput(inputData:Array):Array{
	var outputData:Array = []; // Output lines
	// For this problem we need to validate every row of data
	var N:int = parseInt(inputData[0][0]);
	// We start with i = 1 because first row have the number of cases
	for(var i:int=1; i <= N; i++){
		var x1:int =  parseInt(inputData[i][0]);
		var y1:int =  parseInt(inputData[i][1]);
		var x2:int =  parseInt(inputData[i][2]);
		var y2:int =  parseInt(inputData[i][3]);
		var x3:int =  parseInt(inputData[i][4]);
		var y3:int =  parseInt(inputData[i][5]);
		
		var TriangleType1:String = "triangle"; // triangle or not a triangle, by default 'triangle'
		var TriangleType2:String = ""; // right, obtuse or acute
		var TriangleType3:String = ""; // isosceles or scalene 
		
		// Validating collinearity
		if( (x1 - x2) * (y1 - y3) == (x1 - x3) * (y1 - y2) ){
			TriangleType1 = "not a triangle";
			// Adds a new line to the output
			outputData.push(StringUtil.substitute("Case #{0}: {1}", i, TriangleType1)); 
		}
		else{
			// Is it right, obtuse or acute?
			var s1:int = (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) // Side 1 ^2
			var s2:int = (x1-x3) * (x1-x3) + (y1-y3) * (y1-y3) // Site 2 ^2
			var s3:int = (x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) // Site 3 ^2
			
			if(s1 == s2 + s3 || s2 == s1 + s3 || s3 == s1 + s2)
				TriangleType2 = "right";
			else
				if(s1 > s2 + s3 || s2 > s1 + s3 || s3 > s1 + s2)
					TriangleType2 = "obtuse";
				else
					TriangleType2 = "acute";
			
			// Is it isosceles or scalene?
			if(s1 == s2 || s2 == s3 || s1 == s3)
				TriangleType3 = "isosceles";
			else
				TriangleType3 = "scalene";
			// Adds a new line to the output
			outputData.push(StringUtil.substitute("Case #{0}: {1} {2} {3}", 
													i, 
													TriangleType3,
													TriangleType2,
													TriangleType1)); 
		}
	}
	return outputData;
}

Working Solution

Attachment	Size
TriangleTrilemma.pdf	182.81 KB
TriangleTrilemma.zip	14.98 KB