Congruent triangles

All submissions for this problem are available.
After learning about congruent triangles in his recent mathematics lesson, Johnny has become very excited. He has even invented an interesting counting problem involving congruent triangles!
Recall that two triangles are congruent if their corresponding sides are equal in length and their corresponding angles are equal in size. A lattice triangle is a triangle such that the coordinates of all its vertices are integers. Johnny's problem can now be described as follows:
You are given an integer M and a lattice triangle ABC all of whose vertices (A, B, and C) are inside rectangle R_{M}. R_{M} is the rectangle having (0,0) as its bottomleft corner and (M,M) as its topright corner. In other words, 0 ≤ x_{A}, y_{A}, x_{B}, y_{B}, x_{C}, y_{C} ≤ M. The problem is to count the number of lattice triangles congruent to ABC also having all their vertices inside the rectangle R_{M}.
Could you help Johnny write a program to solve this problem?
Input
The first line contains t, the number of test cases (about 10). Then t test cases follow. Each test case has the following form:
 The first line contains two numbers M and K (1 ≤ M ≤ 1000, 1 ≤ K ≤ 1000). K is the number of given triangles.
 Each line in the next K lines contains 6 integers x_{A}, y_{A}, x_{B}, y_{B}, x_{C}, y_{C} (0 ≤ x_{A}, y_{A}, x_{B}, y_{B}, x_{C}, y_{C} ≤ M) describing a triangle ABC. It is guaranteed that ABC is always a triangle (i.e., nondegenerate).
The input for successive test cases is separated by a blank line.
Output
For each test case, output a line containing the string "Case #T:" where T should be replaced by the corresponding test case number.
Then, K lines should follow, each line containing the number of triangles having vertices inside the rectangle R_{M}, congruent to the corresponding triangle given in the input.
Print a blank line after each test case.
Example
Input: 2 2 2 0 0 0 2 2 0 0 0 1 1 2 0 3 2 0 0 0 2 2 0 0 0 1 1 2 0 Output: Case #1: 4 8 Case #2: 16 24
Output details
The 8 triangles congruent to the second triangle (in the first test case) are presented in the following figure:
Author:  admin 
Tags  admin 
Date Added:  15092009 
Time Limit:  0.141429 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, TEXT 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions