// Find all triangles with area >0 // http://www.frank-buss.de/challenge/index.html // Tobias Guentner #include #include #include #include #include using namespace std; #define ElementCount(arr) (sizeof(arr)/sizeof(*arr)) typedef int Point; typedef unsigned LineIndex; const Point EndOfLine = -1; struct Triangle { Point p1, p2, p3; }; void AddLine(LineIndex* lines, int index, set& result); void MakeTriangle(set& result); Point FindCross(LineIndex firstLine, LineIndex secondLine); // all points are connected to lines const Point g_line1[] = { 0, 1, EndOfLine }; const Point g_line2[] = { 0, 2, 4, 6, EndOfLine }; const Point g_line3[] = { 0, 3, 7, 9, EndOfLine }; const Point g_line4[] = { 0, 5, 8, 10, EndOfLine }; const Point g_line5[] = { 1, 2, 3, 5, EndOfLine }; const Point g_line6[] = { 1, 4, 7, 8, EndOfLine }; const Point g_line7[] = { 1, 6, 9, 10, EndOfLine }; // store all lines in an array for easier access const struct Line { unsigned length; const Point* points; } g_lines[] = { ElementCount(g_line1), g_line1, ElementCount(g_line2), g_line2, ElementCount(g_line3), g_line3, ElementCount(g_line4), g_line4, ElementCount(g_line5), g_line5, ElementCount(g_line6), g_line6, ElementCount(g_line7), g_line7, 0, 0 }; bool operator<(const Triangle& lhs, const Triangle& rhs) { if(lhs.p1 < rhs.p1) return true; if(lhs.p1 > rhs.p1) return false; if(lhs.p2 < rhs.p2) return true; if(lhs.p2 > rhs.p2) return false; if(lhs.p3 < rhs.p3) return true; return false; } ostream& operator<<(ostream& os, const Triangle& t) { return cout << '{' << t.p1 << ',' << t.p2 << ',' << t.p3 << '}'; } int main() { try { set result; MakeTriangle(result); copy(result.begin(), result.end(), ostream_iterator(cout, "\n")); cout << "Total: " << result.size() << endl; } catch(const exception& e) { cerr << "Fatal error: " << e.what() << endl; } return 0; } // Test whether a given lines intersects other lines // Note: Must make sure to return true // if no lines have been tested class CrossTester : public unary_function { public: CrossTester(LineIndex line) : m_line(line), m_intersect(true) { } void operator()(LineIndex l) { m_intersect = m_intersect && FindCross(m_line, l) != EndOfLine; } operator bool() const { return m_intersect; } private: LineIndex m_line; bool m_intersect; }; // Finds a common point for two lines // returns EndOfLine if the lines do not intersect Point FindCross(LineIndex firstLine, LineIndex secondLine) { const Line& first = g_lines[firstLine]; const Line& second = g_lines[secondLine]; for(unsigned firstPoint = 0; firstPoint < first.length; ++firstPoint) { // does the second line go through that point? const Point* begin = second.points; const Point* end = second.points + second.length; Point currentPoint = first.points[firstPoint]; if(find(begin, end, currentPoint) != end) return currentPoint; } // Not found return EndOfLine; } void MakeTriangle(set& result) { // since every line can occur only once in a // triangle (empty triangles are forbidden), // I can pick three random lines and // see if they touch somewhere result.clear(); // stores the index of every line that has been used LineIndex lines[3]; // start of recursion AddLine(lines, 0, result); } // Helper for MakeTriangle: This function recursively // adds lines to the triangle and adds complete // triangles to "result" void AddLine(LineIndex* lines, int index, set& result) { // Pick any line for(LineIndex currentLine = 0; g_lines[currentLine].length > 0; ++currentLine) { // test if this line has already been used if(find(lines, lines + index, currentLine) != lines + index) continue; // test if this line crosses all previous lines if(!for_each(lines, lines + index, CrossTester(currentLine))) continue; // this line is valid, so store it lines[index] = currentLine; if(index != 2) { // add another line AddLine(lines, index + 1, result); } else { // end of recursion // find all corners and store the new triangle Point points[3] = { FindCross(lines[0], lines[1]), FindCross(lines[1], lines[2]), FindCross(lines[2], lines[0]) }; // must only contain valid points assert(points[0] != EndOfLine); assert(points[1] != EndOfLine); assert(points[2] != EndOfLine); // sort all points // (this is necessary because {p1,p2,p3} // and {p2,p3,p1} would be different // triangles otherwise) sort(points, points + 3); // If all three points are equal, have an // empty triangle. Sort them out. if(points[0] != points[1] || points[1] != points[2]) { Triangle t = { points[0], points[1], points[2] }; result.insert(t); } } } }