#include #include #include #include #include #include #include #include #include #include using namespace std; // CGAL Kernel for 2D points. typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef K::Point_2 Point; // Structure representing a cluster. struct Cluster { // Indices (referring to the original input) of the points in this cluster. vector pts; // The minimum index (lowest index among all points in the cluster). int minIndex; // The "size" (number of points) in the cluster. int size; // The string representation of the cluster. // For a single point (xi,yi), the representation is "[(xi,yi)]". // For a merged cluster, if its two subclusters have string forms A and B, then the // representation is "[AB]" if A contains the lowest–indexed point, or "[BA]" otherwise. string rep; }; // Given the input arrays, produce the string for a single–point cluster. string formatPointCluster(int xi, int yi) { ostringstream oss; oss << "[(" << xi << "," << yi << ")]"; return oss.str(); } // The clustering algorithm: given coordinates in vectors x and y, returns the final cluster string. string solve(const vector& x, const vector& y) { int n = x.size(); // Build CGAL points. vector points; for (int i = 0; i < n; i++) { points.push_back(Point(x[i], y[i])); } // Initialize each point as its own cluster. vector clusters; for (int i = 0; i < n; i++) { Cluster c; c.pts.push_back(i); c.minIndex = i; c.size = 1; c.rep = formatPointCluster(x[i], y[i]); clusters.push_back(c); } // While more than one cluster remains, merge the two with the smallest average linkage distance. while (clusters.size() > 1) { double bestDist = numeric_limits::infinity(); int bestI = -1, bestJ = -1; // For every pair of clusters, compute the average distance. for (int i = 0; i < clusters.size(); i++) { for (int j = i + 1; j < clusters.size(); j++) { double sum = 0.0; // For each pair of points (p in cluster[i], q in cluster[j]), sum the Euclidean distance. for (int idxA : clusters[i].pts) { for (int idxB : clusters[j].pts) { // Compute squared distance and then take the square root. double d2 = CGAL::to_double(CGAL::squared_distance(points[idxA], points[idxB])); double d = sqrt(d2); sum += d; } } double avg = sum / (clusters[i].size * clusters[j].size); if (avg < bestDist) { bestDist = avg; bestI = i; bestJ = j; } } } // Merge clusters bestI and bestJ. Cluster A = clusters[bestI]; Cluster B = clusters[bestJ]; Cluster merged; // The points in the merged cluster are the union of the two. merged.pts = A.pts; merged.pts.insert(merged.pts.end(), B.pts.begin(), B.pts.end()); merged.size = A.size + B.size; merged.minIndex = min(A.minIndex, B.minIndex); // The ordering in the new string is determined by which cluster has the lower minIndex. if (A.minIndex < B.minIndex) merged.rep = "[" + A.rep + B.rep + "]"; else merged.rep = "[" + B.rep + A.rep + "]"; // Remove the two merged clusters from the list. // Remove the one with the larger index first to avoid shifting. if (bestI < bestJ) { clusters.erase(clusters.begin() + bestJ); clusters.erase(clusters.begin() + bestI); } else { clusters.erase(clusters.begin() + bestI); clusters.erase(clusters.begin() + bestJ); } // Add the new merged cluster. clusters.push_back(merged); } // Return the final cluster's string representation. return clusters[0].rep; } // Example usage. #ifdef UNIT_TEST #include int main(){ // Example from the problem statement. vector x = {5, 17, 5}; vector y = {4, 4, 9}; string result = solve(x, y); cout << result << endl; // Expected: "[[[(5,4)][(5,9)]][(17,4)]]" assert(result == "[[[(5,4)][(5,9)]][(17,4)]]"); return 0; } #else int main(){ // Read input from standard input if needed. // For example, first integer n (number of points), then n integers for x, then n integers for y. int n; cin >> n; vector x(n), y(n); for (int i = 0; i < n; i++) cin >> x[i]; for (int i = 0; i < n; i++) cin >> y[i]; cout << solve(x, y) << endl; return 0; } #endif