//---------------------------------------------------------------------
// enigma1370.c (c) 2006 by Charles Petzold
//
// "Pair of Quadrilaterals" by Richard England, New Scientist, 10 December 2005
//
// Two quadrilaterals with opposite corners joined to make four triangles.
// Triangles have integral lengths <= 20.
// The angles in the center are 60, 120, 90, and 90 degrees.
// Two solutions: What's the difference in the perimeters?
//----------------------------------------------------------------------

#include <math.h>
#include <stdio.h>
#define Pi (acos(-1))

// Structure for storing all rectangles that have integral sides <= 20
// and at least one angle equal to 60, 90, or 120. 
// 'a' is that angle, and l3 is always opposite that angle.

typedef struct
{
	float a;
	int l1, l2, l3;
}
TRIANGLE;

// Function to allow comparing doubles that may be just a little different.

int Equals(double d1, double d2)
{
	return fabs(d1 - d2) < 0.00001;
}

// This function finds all the triangles with integral sides <= 20 and 
// at least one angle equal to 60, 90, or 120.
// If the argument is null, the function just counts.
// Otherwise it fills up the array.

int FindTriangles(TRIANGLE * pTriangle)
{
	int l1, l2, l3;
	double a1, a2, a3;
	int count = 0;

	// Loop through the three sides

	for (l1 = 1; l1 <= 20; l1++)
	for (l2 = l1; l2 <= 20; l2++)
	for (l3 = l2; l3 < l1 + l2; l3++)
	{
		// Calculate largest angle by cosine rule.

		a3 = 180 * acos((double)(l1 * l1 + l2 * l2 - l3 * l3) / (2 * l1 * l2)) / Pi;

		// Calculate smallest angle by sine rule.
		a1 = 180 * asin(l1 * sin(Pi * a3 / 180) / l3) / Pi;

		// Calculate middle angle.
		a2 = 180 - a1 - a3;

		// The middle angle must equal 60, or the largest 90 or 120.
		if (Equals(a2, 60) || Equals(a3, 90) || Equals(a3, 120))
		{
			// printf("%i %i %i: ", l1, l2, l3);
			// printf("%f %f %f\n", a1, a2, a3);

			// If the largest angle is 90 or 120, store the triangle
			// twice with smaller sides switched.
			// (Stored twice will make later calcs easier.)

			if (Equals(a3, 90) || Equals(a3, 120))
			{
				if (pTriangle)
				{
					pTriangle[count].a = a3;
					pTriangle[count].l1 = l1;
					pTriangle[count].l2 = l2;
					pTriangle[count].l3 = l3;
				}
				count ++;

				if (pTriangle)
				{
					pTriangle[count].a = a3;
					pTriangle[count].l1 = l2;
					pTriangle[count].l2 = l1;
					pTriangle[count].l3 = l3;
				}
				count ++;
			}

			// If the smallest angle is 60, it's a 60-60-60
			// All three sides are the same.
			// Just store it once.

			else if (Equals(a1, 60))
			{
				if (pTriangle)
				{
					pTriangle[count].a = 60;
					pTriangle[count].l1 = l1;
					pTriangle[count].l2 = l2;
					pTriangle[count].l3 = l3;
				}
				count ++;
			}

			// Otherwise, a2 is 60. Store the triangle twice.

			else
			{
				if (pTriangle)
				{
					pTriangle[count].a = 60;
					pTriangle[count].l1 = l1;
					pTriangle[count].l2 = l3;
					pTriangle[count].l3 = l2;
				}
				count ++;

				if (pTriangle)
				{
					pTriangle[count].a = 60;
					pTriangle[count].l1 = l3;
					pTriangle[count].l2 = l1;
					pTriangle[count].l3 = l2;
				}
				count ++;
			}

		}
	}
	return count;
}


int main(void)
{
	TRIANGLE * pTriangle;
	int i, count, i1, i2, i3, i4;

	// Count the triangles
	count = FindTriangles(0);

	// Allocate memory for them.
	pTriangle = (TRIANGLE *) malloc(count * sizeof(TRIANGLE));

	// Store the triangles
	FindTriangles(pTriangle);

	// Print out triangles
	for (i = 0; i < count; i++)
		printf("%i. %f %i %i %i\n", i, pTriangle[i].a, pTriangle[i].l1, pTriangle[i].l2, pTriangle[i].l3);

	// Loop through triangles
	for (i1 = 0; i1 < count; i1++)
	{
		// Want one with 'a' equal to 60
		if (Equals(pTriangle[i1].a, 60))
		{
			// Loop through triangles
			for (i2 = 0; i2 < count; i2++)
			{
				// Second triangle 'a' is 120 and side matches with first
				if (Equals(pTriangle[i2].a, 120) && 
 					pTriangle[i1].l2 == pTriangle[i2].l1)
				{
					for (i3 = 0; i3 < count; i3++)
					{
						// Third triangle is 90 and side matches with second
						if (Equals(pTriangle[i3].a, 90) &&
							pTriangle[i2].l2 == pTriangle[i3].l1)
						{
							for (i4 = 0; i4 < count; i4++)
							{
								// Fourth triangle is 90 and sides match
								// with first and third
								if (Equals(pTriangle[i4].a, 90) &&
									pTriangle[i3].l2 == pTriangle[i4].l1 &&
									pTriangle[i4].l2 == pTriangle[i1].l1)
								{
									// Successful!
									int perimeter = pTriangle[i1].l3 + pTriangle[i2].l3 + pTriangle[i3].l3 + pTriangle[i4].l3;
									printf("Indices: %i %i %i %i Perimeter: %i\n", i1, i2, i3, i4, perimeter);
								}
							}
						}
					}
				}
			}
		}
	}
	return 0;
}