You must find the minimum cost triangulation of a convex polygon. A triangulation is formed by drawing diagonals between nonadjacent vertices, and the diagonals never intersect with each other.
Input: Point[] points = {new Point(0, 0), new Point(1, 0), new Point(2, 1), new Point(1, 2), new Point(0, 1)}; Output: 13.071067811865476 Explanation: There are 2 diagonals, from point 2 to 5 and prom point 3 to 5 and their sum is 13.071067811865476. |
Solution:
1. static class Point { 2. int x; 3. int y; 4. 5. Point(int x, int y) { 6. this.x = x; 7. this.y = y; 8. } 9. } 10. 11. static double getDistanceBetweenPoints(Point p1, Point p2) { 12. return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); 13. } 14. 15. static double getTrianglePerimeter(Point[] points, int i, int j, int k) { 16. Point p1 = points[i]; 17. Point p2 = points[j]; 18. Point p3 = points[k]; 19. return getDistanceBetweenPoints(p1, p2) + getDistanceBetweenPoints(p2, p3) + getDistanceBetweenPoints(p3, p1); 20. } 21. 22. static double findMinimumCostForPolygonTriangulation(Point[] points) { 23. int n = points.length; 24. if (n < 3) { 25. return 0; 26. } 27. double[][] triangulations = new double[n][n]; 28. 29. for (int gap = 0; gap < n; gap++) { 30. for (int i = 0, j = gap; j < n; i++, j++) { 31. if (j < i + 2) { 32. triangulations[i][j] = 0.0; 33. } else { 34. triangulations[i][j] = Integer.MAX_VALUE; 35. for (int k = i + 1; k < j; k++) { 36. double triangulation = triangulations[i][k] + triangulations[k][j] + getTrianglePerimeter(points, i, j, k); 37. if (triangulations[i][j] > triangulation) { 38. triangulations[i][j] = triangulation; 39. } 40. } 41. } 42. } 43. } 44. return triangulations[0][n - 1]; 45. } 46.