#6213. 「美团 CodeM 决赛」radar

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

Lyra 在玩一款游戏,在这款游戏中,Lyra 要在国境线上安装一列雷达,国境线可以看做一个数轴,第 ii 个雷达横坐标在 xix_i 的位置,高度最大为 yiy_i。雷达可以向下方至斜下方 4545^\circ 角范围内扫描,所以 (x0,y0)(x_0,y_0) 点的雷达可以扫描满足 0yy0xx00 \leq y \leq y_0-|x-x_0| 的点组成的区域,若干个雷达的扫描区域是每个雷达扫描点集的并。

1.jpg

ii 个雷达初始时高度为 00,Lyra 可以花费 cic_i 元将其高度提升 11,注意高度只能是整数。所有雷达布置完之后 Lyra 对于雷达能覆盖到的二维区域,获得等同于其面积的收入。

现在给定所有的 xi,yi,cix_i,y_i,c_i 求 Lyra 的最大净收入(即最后的收入减去布置雷达的花费)。

输入格式

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

对于每组数据,第一行一个整数 nn 表示雷达数目,接下来 nn 行每行三个正整数 xi,yi,cix_i,y_i,c_i 意义如题意所述。

输出格式

对于每组数据输出一行一个实数表示最大净收入,保留两位小数。

样例

样例输入

2
2
0 4 1
4 4 3
2
0 4 0
4 100 100

样例输出

12.00
16.00

样例解释

对于第一组数据,我们可以这样设定雷达的高度:

2.jpg

或者

3.jpg

对于第二组数据,两种方案中只有后者是最优方案。

数据范围与提示

T500T \leq 500
1n1051 \leq n \leq 10^5n106\sum n \leq 10^6
0xi,yi,ci1080 \leq |x_i|,y_i,c_i \leq 10^8