Puzzle - Triangle Trilemma

[FriedEgg]

Hi everyone,

It has been a very long time since I last posted one of these puzzles.  This one comes from a fantastic blog http://www.programmingpraxis.com. And the Google Code Jam Beta 2008.

Problem

You're interested in writing a program to classify triangles. Triangles can be classified according to their internal angles. If one of the internal angles is exactly 90 degrees, then that triangle is known as a "right" triangle. If one of the internal angles is greater than 90 degrees, that triangle is known as an "obtuse" triangle. Otherwise, all the internal angles are less than 90 degrees and the triangle is known as an "acute" triangle.

Triangles can also be classified according to the relative lengths of their sides. In a "scalene" triangle, all three sides have different lengths. In an "isosceles" triangle, two of the sides are of equal length. (If all three sides have the same length, the triangle is known as an "equilateral" triangle, but you can ignore this case since there will be no equilateral triangles in the input data.)

Your program must determine, for each set of three points, whether or not those points form a triangle. If the three points are not distinct, or the three points are collinear, then those points do not form a valid triangle. (Another way is to calculate the area of the triangle; valid triangles must have non-zero area.) Otherwise, your program will classify the triangle as one of "acute", "obtuse", or "right", and one of "isosceles" or "scalene".

Input

The first line of input gives the number of cases, N. N test cases follow. Each case is a line formatted as

x1 y1 x2 y2 x3 y3

Output

For each test case, output one line containing "Case #x: " followed by one of these strings:

• isosceles acute triangle
• isosceles obtuse triangle
• isosceles right triangle
• scalene acute triangle
• scalene obtuse triangle
• scalene right triangle
• not a triangle

Limits

1 ≤ N ≤ 100,
x1, y1, x2, y2, x3, y3 will be integers.

Small dataset

0 ≤ x1, y1, x2, y2, x3, y3 ≤ 9

Large dataset

-1000 ≤ x1, y1, x2, y2, x3, y3 ≤ 1000

Sample

Input	Output
8 0 0 0 4 1 2 1 1 1 4 3 2 2 2 2 4 4 3 3 3 3 4 5 3 4 4 4 5 5 6 5 5 5 6 6 5 6 6 6 7 6 8 7 7 7 7 7 7	Case #1: isosceles obtuse triangle Case #2: scalene acute triangle Case #3: isosceles acute triangle Case #4: scalene right triangle Case #5: scalene obtuse triangle Case #6: isosceles right triangle Case #7: not a triangle Case #8: not a triangle

Short Version of the Problem:

The problem is to accept three points as input, determine if they form a triangle, and, if they do, classify it at equilateral (all three sides the same), isoceles (two sides the same, the other different), or scalene (all three sides different), and also classify it as acute (all three angles less than 90 degrees), obtuse (one angle greater than 90 degrees) or right (one angle equal 90 degrees).

My answer below:

data _null_ ;

    length typeOfTriangle $ 32 ;

    array x[3] _temporary_ ;

  array y[3] _temporary_ ;

    input x[1] y[1] x[2] y[2] x[3] y[3] @ ;

  if ( x[1] = x[2] = x[3] ) or ( y[1] = y[2] = y[3] ) then do;

     typeOfTriangle = 'Not A Triangle' ;

     put typeOfTriangle $32. ' :: ' _infile_ ;

  return ;

   end;

  array d[3] _temporary_ ;

    d[1] = sqrt( ( x[2] - x[1] ) ** 2 + ( y[2] - y[1] ) ** 2 ) ;

  d[2] = sqrt( ( x[3] - x[1] ) ** 2 + ( y[3] - y[1] ) ** 2 ) ;

  d[3] = sqrt( ( x[3] - x[2] ) ** 2 + ( y[3] - y[2] ) ** 2 ) ;

    if ( ( d[1] = 0 ) or ( d[2] = 0 ) or ( d[3] = 0 ) ) then do;

     put 'Not a triangle :: ' _infile_ ;

  return ;

   end;

    else if ( d[1] = d[2] = d[3] ) then do;

     typeOfTriangle = 'Equilateral' ;

   end;

  else if ( ( d[1] = d[2] ) or ( d[2] = d[3] ) or ( d[3] = d[1] ) ) then do;

     typeOfTriangle = 'Isosceles'   ;

   end;

  else do;

     typeOfTriangle = 'Scalene'     ;

   end;

  call sortn( of d

) ;

    degree = round( arcos( ( sum( d[1] ** 2 , d[2] ** 2 ) - ( d[3] ** 2 ) ) / ( 2 * d[1] * d[2] ) ) * ( 180 / constant( 'pi' ) ) , .0000001 ) ;

    if ( degree > 90 ) then do;

     typeOfTriangle = catx( ' ' , typeOfTriangle , 'Obtuse Triangle' ) ;

   end;

  else if ( degree = 90 ) then do;

     typeOfTriangle = catx( ' ' , typeOfTriangle , 'Right Angle Triangle' ) ;

   end;

    else do;

     typeOfTriangle = catx( ' ' , typeOfTriangle , 'Acute Triangle' ) ;

   end;

  put typeOfTriangle $32. ' :: ' _infile_ ;

    cards ;

0 0 0 4 1 2

1 1 1 4 3 2

2 2 2 4 4 3

3 3 3 4 5 3

4 4 4 5 5 6

5 5 5 6 6 5

6 6 6 7 6 8

7 7 7 7 7 7

;

run;

[Haikuo]

It took some hard coding but since it is triangle problem instead of a Hectagon (100 angles),so it wasn't too bad. Because of many mathematic operations and comparison, you have to properly apply Round() all the time, or the SAS precision issue will eat you alive.

data have;

infile cards truncover;

input x1 y1 x2 y2 x3 y3;

if _n_>1 then output;

cards;

8

0 0 0 4 1 2

1 1 1 4 3 2

2 2 2 4 4 3

3 3 3 4 5 3

4 4 4 5 5 6

5 5 5 6 6 5

6 6 6 7 6 8

7 7 7 7 7 7

;

data _null_;

length side $ 20 angle $20;

   set have;

   array agl alpha beta gamma;

a=round(sqrt((x1-x2)**2+(y1-y2)**2),0.01);

b=round(sqrt((x1-x3)**2+(y1-y3)**2),0.01);

c=round(sqrt((x3-x2)**2+(y3-y2)**2),0.01);

if a*b*c ne 0 then do;

alpha=round(arcos((b**2+c**2-a**2)/(2*b*c)),0.01);

beta=round(arcos((a**2+c**2-b**2)/(2*a*c)),0.01);

gamma=round(arcos((b**2+a**2-c**2)/(2*b*a)),0.01);

end;

if a=b or a=c or b=c then side='isosceles';

else side='scalene';

do over agl;

  if round(cos(agl),0.1)=0 then angle='right';

  else if round(cos(agl),0.1)<0 then angle='obtuse';

  else angle =coalescec(angle,'acute');

end;

if not (a+b>c and a+c>b and b+c>a) then put "Case #" _n_ ": "  "not a triangle";

else put  "Case #" _n_ ": " side " " angle " triangle";

run;

Case #1 : isosceles obtuse  triangle

Case #2 : scalene  acute  triangle

Case #3 : isosceles  acute  triangle

Case #4 : scalene  right  triangle

Case #5 : scalene  obtuse  triangle

Case #6 : isosceles  right  triangle

Case #7 : not a triangle

Case #8 : not a triangle

Haikuo