1684: 密度聚类（DBSCAN）

1. ε 邻域：对于样本点p，其 ε 邻域定义为所有与p的欧几里得距离≤ε的样本点集合（包含p自身）。
2. 核心点：若样本点p的 ε 邻域内的样本点数≥MinPts，则p为核心点；否则为非核心点。
3. 直接密度可达：若样本点q在核心点p的 ε 邻域内，则称q从p直接密度可达。
4. 密度可达：若存在样本点序列p1,p2,...,pn，其中p1=p，pn=q，且pi+1从pi直接密度可达，则称q从p密度可达。
5. 密度连通：若存在样本点o，使得p和q都从o密度可达，则称p和q密度连通。
6. 聚类定义：一个聚类是最大的密度连通样本点集合；不属于任何聚类的样本点为噪声点（标记为 - 1）。
7. 聚类编号规则：按核心点被首次发现的顺序分配聚类编号（从 0 开始），非核心点若与核心点密度连通则归入对应聚类。

• n：样本点数量（1≤n≤10⁴）
• d：样本点的维度（1≤d≤5）
• ε：邻域半径（0<ε≤10⁴，浮点数）
• MinPts：核心点的最小邻域点数（2≤MinPts≤100）

样例输入

样例输出

0
0
0
-1
1
1
1
-1

样例解释

• 前 3 个点的 ε 邻域（1.5）内互相包含，点数≥3，构成核心点，归为聚类 0；
• 第 4 个点的 ε 邻域内只有自身，为噪声点；
• 第 5-7 个点的 ε 邻域内互相包含，点数≥3，构成核心点，归为聚类 1；
• 第 8 个点的 ε 邻域内只有自身，为噪声点。

数据范围

• 1≤n≤104，1≤d≤5，0<ε≤10⁴
• 2≤MinPts≤100
• 所有浮点数精度保证在10⁻⁶以内