import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * @author Babu Kalakrishnan
 */
public class TrianglesProblem
{
	private Line[] lines;
	private int maxPoint;

	/**
	 * Define the problem domain with the specified set of lines
	 */
	public TrianglesProblem(Line[] lines)
	{
		this.lines = lines;
		maxPoint = 0;
		for (int i = 0; i < lines.length; i++)
		{
			int n = lines[i].getLargestPoint();
			if (n > maxPoint)
				maxPoint = n;
		}
	}

	/**
	 * Returns true if the triad a/b/c is a valid triangle
	 */
	private boolean isValidTriangle(int a, int b, int c)
	{
		boolean b1 = false, b2 = false, b3 = false;
		for (int i = 0; i < lines.length; i++)
		{
			Line l = lines[i];
			if (!b1 && l.isValidSegment(a, b))
			{
				if (l.indexOnLine(0, c) >= 0)
					return false;
				b1 = true;
			} else if (!b2 && l.isValidSegment(a, c))
			{
				if (l.indexOnLine(0, b) >= 0)
					return false;
				b2 = true;
			} else if (!b3 && l.isValidSegment(b, c))
			{
				if (l.indexOnLine(0, a) >= 0)
					return false;
				b3 = true;
			}
			if (b1 && b2 && b3)
				return true;
		}
		return false;
	}

	/**
	 * Returns a List containing all valid triangles found in this problem
	 * domain
	 */
	public List getTriangles()
	{
		List list = new ArrayList();
		for (int i = 0; i <= maxPoint; i++)
		{
			for (int j = i + 1; j <= maxPoint; j++)
				for (int k = j + 1; k <= maxPoint; k++)
					if (isValidTriangle(i, j, k))
						list.add(new int[]
							{
									i, j, k
							});
		}
		return list;
	}

	/**
	 * Class representing a line that has muliple points on it. Each point is
	 * represented by an integer number, and therefore the line is defined as an
	 * array of ints
	 */
	static class Line
	{
		int[] points;

		/**
		 * Construct a line through the specified points Ensure that the points
		 * array is sorted in ascending order so that searches for points can
		 * fail early
		 * 
		 * @param points
		 */
		Line(int[] points)
		{
			this.points = points;
			Arrays.sort(points);
		}

		/**
		 * 
		 * @return The largest point on this line
		 */
		int getLargestPoint()
		{
			return points[points.length - 1];
		}

		/**
		 * Returns true if the pair n1/n2 forms a line segment falling on this
		 * line
		 */
		boolean isValidSegment(int n1, int n2)
		{
			int ind = indexOnLine(0, n1);
			if (ind >= 0)
				return indexOnLine(ind + 1, n2) > 0;
			else
				return false;
		}

		/**
		 * Returns the index of point "target" in the points array - starting
		 * the search from index searchIndex Returns -1 if point is not found
		 */
		int indexOnLine(int startIndex, int target)
		{
			while (startIndex < points.length)
			{
				if (target == points[startIndex])
					return startIndex;
				if (target < points[startIndex])
					return -1;
				startIndex++;
			}
			return -1;
		}
	}

	public static void main(String[] args)
	{
		TrianglesProblem tr = new TrianglesProblem(new Line[]
			{
					new Line(new int[]
						{
								0, 1
						}), new Line(new int[]
						{
								0, 2, 4, 6
						}), new Line(new int[]
						{
								0, 3, 7, 9
						}), new Line(new int[]
						{
								0, 5, 8, 10
						}), new Line(new int[]
						{
								1, 2, 3, 5
						}), new Line(new int[]
						{
								1, 4, 7, 8
						}), new Line(new int[]
						{
								1, 6, 9, 10
						})
			});

		List l = tr.getTriangles();
		int n = l.size();
		System.out.println("Total triangles = " + n);
		for (int i = 0; i < n; i++)
		{
			int[] triangle = (int[]) l.get(i);
			System.out.println("P" + triangle[0] + "-P" + triangle[1] + "-P"
					+ triangle[2]);
		}
	}

}