题目内容

文档检索系统需要判断片段是否相关。本题将每个文档片段视为平面上的一个点。为提高检索效率，要判定两个片段是否属于同一语义簇：若它们密度相连，则认为语义相近。

概念说明

给定一组点，以及两个参数：邻域半径 $\varepsilon$、最小点数 $MinPts$。

• $\varepsilon$-邻域：点 $p$ 的 $\varepsilon$-邻域是所有到 $p$ 的距离不超过 $\varepsilon$ 的点（含 $p$ 自身）。距离取欧氏距离$$dist(p,q)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$
• 核心点：若点 $p$ 的 $\varepsilon$-邻域内至少有 $MinPts$ 个点，则 $p$ 是核心点。
• 密度相连：点 $p$ 与点 $q$ 密度相连，当且仅当存在核心点 $o$，从 $o$ 出发能分别沿着核心点的“路径”走到 $p$ 和 $q$，路径上的每一步，都必须从一个核心点走到其 $\varepsilon$-邻域内的某个点。

几个直接推论：

• 同一簇内的点彼此密度相连
• 噪声点（未落入任何核心点的 $\varepsilon$-邻域）不与任何点密度相连
• 两个边界点（位于某核心点邻域内、自身却不是核心点）若被同一个核心点覆盖，则密度相连

输入描述

第一行四个数：$N$、$M$、$\varepsilon$、$MinPts$

• $N$：点的数量
• $M$：询问数量
• $\varepsilon$：邻域半径
• $MinPts$：成为核心点所需的最少邻域点数

接下来 $N$ 行：每行两个浮点数 $x_i$、$y_i$，按顺序给出编号为 $0$ 到 $N-1$ 的点的坐标。

接下来 $M$ 行：每行两个整数 $a$、$b$，询问点 $a$ 与点 $b$ 是否密度相连。

数据范围

• $1 \le N,M \le 1000$
• $0 < \varepsilon \le 1000$
• $2 \le MinPts \le N$
• $-10000 \le$ 坐标值 $\le 10000$

输出描述

共 $M$ 行，每行一个整数：

• $1$ 表示密度相连
• $0$ 表示不密度相连

补充说明

提示：可按密度聚类 / 密度可达来做判定。

样例1

输入

6 4 2.0 3
0.0 0.0
1.2 0.0
0.4 1.0
12.0 0.0
12.5 0.4
6.0 6.0
0 2
0 3
3 4
1 5

输出

1
0
0
0

说明

$\varepsilon=2.0$，$MinPts=3$。

点 $0,1,2$ 两两距离分别为 $1.2$、$\sqrt{1.16}\approx 1.077$、$\sqrt{1.64}\approx 1.281$，均不超过 $2.0$，每个点的邻域大小都是 $3$，因此都是核心点，彼此密度相连。

点 $3$ 与点 $4$ 相距 $\sqrt{0.41}\approx 0.640\le 2.0$，但各自邻域只有 $2$ 个点，不是核心点，也没有核心点能走到它们，因此是噪声点，彼此不密度相连。

点 $5$ 邻域只有自身，同样是噪声点。

样例2

输入

8 4 2.0 3
0.0 0.0
1.5 0.0
0.3 1.4
3.2 0.2
8.0 8.0
8.6 8.2
8.3 9.5
0.0 8.0
0 2
0 3
4 5
3 4

输出

1
1
1
0

说明

$\varepsilon=2.0$，$MinPts=3$。

点 $0,1,2$ 两两距离分别为 $1.5$、$\sqrt{2.05}\approx 1.432$、$\sqrt{3.4}\approx 1.844$，均为核心点。点 $3$ 到点 $1$ 的距离为 $\sqrt{2.93}\approx 1.712$，落入点 $1$ 的邻域，但自身邻域只有 $2$ 个点，是边界点；从核心点 $1$ 可以走到点 $0$ 与点 $3$，故 $0$ 与 $3$ 密度相连。

点 $4,5,6$ 两两距离分别为 $\sqrt{0.4}\approx 0.632$、$\sqrt{2.34}\approx 1.529$、$\sqrt{1.78}\approx 1.334$，都是核心点，形成一个独立的簇。

点 $3$ 与点 $4$ 分属不同簇，不密度相连。点 $7$ 是噪声点。