public class Solution8 extends Solution {
public Solution8() {
super(8);
}
public static void main(String[] args) {
Solution8 solution = new Solution8();
solution.testPartTwo();
}
@Override
String solvePartOne(String inputData) {
String[] lines = inputData.trim().split("\n");
int n = lines.length;
long[][] pts = new long[n][3];
for (int i = 0; i < n; i++) {
String[] p = lines[i].split(",");
pts[i][0] = Long.parseLong(p[0]);
pts[i][1] = Long.parseLong(p[1]);
pts[i][2] = Long.parseLong(p[2]);
}
int m = n * (n - 1) / 2;
long[][] edges = new long[m][3];
int idx = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
long dx = pts[i][0] - pts[j][0];
long dy = pts[i][1] - pts[j][1];
long dz = pts[i][2] - pts[j][2];
long d = dx * dx + dy * dy + dz * dz;
edges[idx++] = new long[]{d, i, j};
}
}
java.util.Arrays.sort(edges, java.util.Comparator.comparingLong(a -> a[0]));
DSU dsu = new DSU(n);
int connections = (n == 20) ? 10 : 1000;
int limit = Math.min(connections, edges.length);
for (int i = 0; i < limit; i++)
dsu.union((int) edges[i][1], (int) edges[i][2]);
java.util.Map map = new java.util.HashMap<>();
for (int i = 0; i < n; i++) {
int r = dsu.find(i);
map.put(r, map.getOrDefault(r, 0) + 1);
}
int[] sizes = map.values().stream().mapToInt(Integer::intValue).toArray();
java.util.Arrays.sort(sizes);
int len = sizes.length;
long res = 1L * sizes[len - 1] * sizes[len - 2] * sizes[len - 3];
return String.valueOf(res);
}
@Override
String solvePartTwo(String inputData) {
String[] lines = inputData.trim().split("\n");
int n = lines.length;
long[][] pts = new long[n][3];
for (int i = 0; i < n; i++) {
String[] p = lines[i].split(",");
pts[i][0] = Long.parseLong(p[0]);
pts[i][1] = Long.parseLong(p[1]);
pts[i][2] = Long.parseLong(p[2]);
}
int m = n * (n - 1) / 2;
long[][] edges = new long[m][3];
int idx = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
long dx = pts[i][0] - pts[j][0];
long dy = pts[i][1] - pts[j][1];
long dz = pts[i][2] - pts[j][2];
long d = dx * dx + dy * dy + dz * dz;
edges[idx++] = new long[]{d, i, j};
}
}
java.util.Arrays.sort(edges, java.util.Comparator.comparingLong(a -> a[0]));
DSU dsu = new DSU(n);
long result = 0;
for (int i = 0; i < edges.length; i++) {
int a = (int) edges[i][1];
int b = (int) edges[i][2];
if (dsu.union(a, b)) {
if (dsu.components == 1) {
result = pts[a][0] * pts[b][0];
break;
}
}
}
return String.valueOf(result);
}
static class DSU {
int[] parent, size;
int components;
DSU(int n) {
parent = new int[n];
size = new int[n];
components = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
boolean union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (size[a] < size[b]) {
int t = a;
a = b;
b = t;
}
parent[b] = a;
size[a] += size[b];
components--;
return true;
}
}
}