bzoj#P2185. Cover

Cover

题目描述

给定一个 l×wl\times w 的矩形(左下角在 (0,0)(0,0),右上角在 (l,w)(l,w)),再给定 nn 个圆,圆的坐标和半径已知。

你的任务是找到一个最小的 kk,使得所有的圆的半径都是原来的 kk 倍,且能完全覆盖整个矩形(注意 kk 可以 <1<1)。

输入格式

第一行一个整数 TT,表示数据组数。

对于每个数据,第一行包括三个整数 n,l,wn,l,w

以下 nn 行,每行三个整数 xi,yi,rix_i,y_i,r_i 表示圆的坐标和半径。

输出格式

仅一行,包含一个最小的实数 kk,保留三位小数。

样例输入

1
1 2 2
1 1 1

样例输出

1.414

数据规模与约定

对于 100%100\% 的数据,1n501\leq n\leq 501l,w1031\leq l,w\leq 10^3T103T\leq 10^3,所有数据均为不超过 10310^3 的非负整数。