Google codejam 2008 contest practice test

This time we will probe Google famous CodeJam contest. We will try to solve codejam 2008 one of practice tests. Test problem is defined as:
-----------------------------------------------------------------------
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.

Sample Input

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

Sample Output

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

-----------------------------------------------------------------------
This time solution is written in Python language. To test this solution you need to have Python interpreter installed. You can install it from www.python.org. For trying this script- paste Sample Input lines into file named 'A-large.in' and place this file into the same folder where below mentioned Python script will be. Script is somewhat fast - 100 sample triangles is analyzed in just 2.2 ms !!!. Script code:

---

#!/usr/bin/env python

import sys, time

def ReadFile():
    """ Read data input file"""
    path = sys.path[0]
    f = open(path + '/A-large.in','r')
    str = f.readlines()
    f.close()
    return str

def IsTriangle(p):
    """Defines triangle by it`s area"""
    area = (p[0]*(p[3]-p[5])+p[2]*(p[5]-p[1])+p[4]*(p[1]-p[3]))
    if area == 0:
        return 'not a triangle'
    else:
        return 'triangle'

def SideType(p):
    """Defines triangle by sides lengths"""
    s1 = ((abs(p[0]-p[2])**2)+(abs(p[1]-p[3])**2))**0.5
    s2 = ((abs(p[0]-p[4])**2)+(abs(p[1]-p[5])**2))**0.5
    s3 = ((abs(p[2]-p[4])**2)+(abs(p[3]-p[5])**2))**0.5
    if s1!=s2 and s1!=s3 and s3!=s2:
        return 'scalene'
    if s1==s2 or s1==s3 or s3==s2:
        return 'isosceles'

def AngleType(p):
    """Defines triangle type by angle.
       Idea based on Pythagorean theorem and somewhat
       empirical hack about 'not perfect' right triangles ->
       for which (a^2+b^2)/c^2 is only approximately 1.
       And the more angle shifts from 90 degrees, the
       more (a^2+b^2)/c^2 relation shifts from 1"""
    s1 = ((abs(p[0]-p[2])**2)+(abs(p[1]-p[3])**2))**0.5
    s2 = ((abs(p[0]-p[4])**2)+(abs(p[1]-p[5])**2))**0.5
    s3 = ((abs(p[2]-p[4])**2)+(abs(p[3]-p[5])**2))**0.5
    k1 = round(float((s1**2)+(s2**2))/float(s3**2),3)
    k2 = round(float((s1**2)+(s3**2))/float(s2**2),3)
    k3 = round(float((s3**2)+(s2**2))/float(s1**2),3)
    
    if k1==1.0 or k2==1.0 or k3==1.0:
        return 'right'
    elif k1<1.0 or k2<1.0 or k3<1.0:
        return 'obtuse'
    else:
        return 'acute'

def ComputeResults():
    out = []
    for i,s in enumerate(ReadFile()):
        pt = map(int,s.rstrip().split())
        if pt.__len__() != 1:
            tr = IsTriangle(pt)
            st = ''
            at = ''
            if tr == 'triangle':
                st = SideType(pt) + ' '
                at = AngleType(pt) + ' '
            tot = 'Case #' + str(i) + ': ' + st + at + tr + '\n'
            out.append(tot)
    return out

def WriteFile(lst):
    """ Write results to data file"""
    path = sys.path[0]
    f = open(path + '/A-large.out','w')
    f.writelines(lst)
    f.close()

if __name__ == '__main__':
    t1 = time.time()*1000
    res = ComputeResults()
    t2 = time.time()*1000
    WriteFile(res)
    print 'Done.'
    print 'Computation time ',round(t2-t1,3),'ms'
    print 'Results are written in file A-large.out'

---

Have fun !