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]); } } }