//--------------------------------------------------------------------- // 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 #include #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; }