// Find all triangles with area >0
// http://www.frank-buss.de/challenge/index.html
// Tobias Guentner <fatbull@users.sourceforge.net>

#include <iostream>
#include <algorithm>
#include <cassert>
#include <set>
#include <iterator>

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<Triangle>& result);
void MakeTriangle(set<Triangle>& 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<Triangle> result;
		MakeTriangle(result);
		copy(result.begin(), result.end(), ostream_iterator<Triangle>(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<LineIndex, void>
{
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<Triangle>& 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<Triangle>& 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);
			}
		}
	}
}