P13820 「LDOI R3」村村振兴

现在共有 $n$ 个存在于平面直角坐标系中的村庄，国家颁布了乡村振兴的政策，你负责修建**一个** 6G 信号基站让村民们都过上有网用的好日子。山地地形险要，在不同的地区修建基站的成本将会提升。 我们定义信号基站坐标为 $(a,b)$，信号强度为 $R$，则一个位于 $(x,y)$ 的村庄能够接受到信号当且仅当 $R^2\ge (x-a)^2+(y-b)^2$。在 $(a,b)$ 修建一个信号强度为 $R$ 的信号基站的成本为 $R\times w(a,b)$。其中 $w(a,b)$ 为该地区的修建难度。 经过地形勘测，你已经得知了地区的修建难度的具体数值，具体地。$w(a,b)$ 由一个圆形区域来决定，该圆有以下属性：圆心 $(x,y)$，半径 $r$，权值 $v$。若 $(a,b)$ 在圆内（包含圆周上）则 $w(a,b)=v$，若 $(a,b)$ 被多个圆包含则取 $v$ 的最大值，若 $(a,b)$ 未被任何圆包含，则 $w(a,b)=1$。这些圆形区域共有 $m$ 个。 你需要修建**一个基站**使得**所有村庄**都能接受到信号且修建的成本**最小**。

第一行两个整数 $n,m$。 随后 $n$ 行，每行两个整数 $x,y$，表示村庄坐标。 随后 $m$ 行，每行先是三个整数 $x,y,r$，然后是一个**至多 $2$ 位小数的实数** $v$，表示一个特殊区域。

输出最小成本，你需要保证答案与标准答案的绝对误差或相对误差不超过 $10^{-5}$。即设你的答案为 $a$，标准答案为 $A$，你需要保证 $\min(|a-A|,\frac{|a-A|}{A})\le 10^{-5}$。

#### 【样例 1 解释】 如下图  #### 【样例 2 解释】 你可以将基站建设于非整数点上。答案为 $\frac{\sqrt{2}}{2}$，你也可以输出 $0.707106781$ 等。 #### 【数据范围与约定】 对于所有的数据，保证： - $1\le n\le 10^4$， - $0\le m\le 8$， - $0\le x,y,r\le 10^5$， - $0