Cluster analysis - Unweighted pair-group average

Clustering is a task of grouping a set of objects in such a way that the objects in the same class are similar to each other and the objects in different classes are distinct. Cluster analysis is employed in many fields such as machine learning, pattern recognition, image analysis, etc.

In this kata, your task is to implement a simple clustering technique called 'Unweighted pair-group average'. This method takes a set of 2D points and the desired number of final clusters. Initially, each point forms its own cluster. The most similar (least distant) clusters are iteratively merged until the target number of clusters is reached.

The distance metric between two clusters is defined as the average distance between all pairs of points from the two clusters. For example: 
```
Cluster 1: (0, 0), (0, 1)
Cluster 2: (4, 3)
Distance = (sqrt((0-4)^2 + (0-3)^2) + sqrt((0-4)^2 + (1-2)^2)) / 2
```

Input:
- ```points``` - a list of 2D points ```[(1, 1), (3, 5), (4, 4), (8, 2), (0, 1)]```
- ```n``` - the desired number of clusters

Output:
- list of clusters, each cluster is a list of points
- points in each cluster should be sorted in ascending order
- the list of clusters should also be sorted in ascending order

Example:
- ```cluster(3, [(1, 1), (3, 5), (4, 4), (8, 2), (0, 1)])```
- should return 
```[ [(0, 1), (1, 1)],
     [(3, 5), (4, 4)],
     [(8, 2)]
   ]
```
   
Notes:
- the coordinates ```(x, y)``` are chosen from interval ```<0, 1000>```
- ```0 < len(points) <= 100```
- ```0 < n <= len(points)```
- there is always only one unique solution
- there are no duplicate points in the input

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from statistics import mean\nfrom itertools import product\nfrom math import sqrt, inf\n\n\ndef distance_between_points(point1, point2):\n    return sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)\n\n\ndef distance_between_clusters(cluster1, cluster2):\n    return mean(\n        distance_between_points(point1, point2) for (point1, point2) in product(cluster1, cluster2)\n    )\n\n\ndef merge_clusters(cluster1, cluster2):\n    return sorted([*cluster1, *cluster2])\n\n\ndef identificator(cluster):\n    return (cluster[0], len(cluster))\n\n\ndef update_distances(clusters, distances):\n    for cluster1 in clusters:\n        for cluster2 in clusters:\n            id1 = identificator(cluster1)\n            id2 = identificator(cluster2)\n            if id1 != id2 and distances.get((id1, id2)) is None:\n                distance = distance_between_clusters(cluster1, cluster2)\n                distances[(id1, id2)] = distance\n                distances[(id2, id1)] = distance\n\n\ndef clear_unactual_distances(distances, cluster1, cluster2):\n    old_ids = [identificator(cluster1), identificator(cluster2)]\n    new_distances = {k: v for k, v in list(distances.items()) if k[0] not in old_ids and k[1] not in old_ids}\n    return new_distances\n                \n\ndef pop_minimal_distance_pair(clusters, distances):\n    minimal_ids = None\n    minimal_distance = 10_000_000\n    for ids_pair, distance in list(distances.items()):\n        if distance < minimal_distance:\n            minimal_distance = distance\n            minimal_ids = ids_pair\n    cluster1 = next(cluster for cluster in clusters if identificator(cluster) == minimal_ids[0])\n    cluster2 = next(cluster for cluster in clusters if identificator(cluster) == minimal_ids[1])\n    clusters.remove(cluster1)\n    clusters.remove(cluster2)\n    return (cluster1, cluster2)\n    \ndef cluster(points, n):\n    clusters = [[point] for point in points]\n    distances = {}\n    while n != len(clusters):\n        update_distances(clusters, distances)\n        cluster1, cluster2 = pop_minimal_distance_pair(clusters, distances)\n        new_cluster = merge_clusters(cluster1, cluster2)\n        clusters.append(new_cluster)\n        distances = clear_unactual_distances(distances, cluster1, cluster2)\n    return sorted(clusters)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'cluster'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5794