#P18502. Huge Oil Platform

Huge Oil Platform

Huge Oil Platform

Jeroen 计划在北海建造一座石油平台。他已经找到 nn 个能够开采石油的位置,并估计了平台能够开采每个位置时所获得的收益。由于平台十分巨大,可以把这些开采位置视为平面上的点;在本题中,地球可以看作平面。

按照规定,平台必须是一个矩形,其方向可以任意旋转。平台本体很便宜,但其四周的安全围栏非常昂贵,因此建造费用等于这个矩形的周长。

位于矩形内部或边界上的所有位置都可以开采,收益为这些位置的收益之和。允许建造宽度和/或高度为 00 的退化矩形:一个单点的周长为 00,长度为 dd 的退化线段矩形的周长为 2d2d。

求能够获得的最大利润,即开采收益总和减去平台建造费用。

输入格式

第一行包含一个整数 nn(1≤n≤4001\le n\le 400),表示候选开采位置数。

接下来 nn 行,每行三个整数 x,y,wx,y,w(0≤x,y≤1060\le x,y\le 10^6,1≤w≤1091\le w\le 10^9),表示一个位置的坐标及开采收益。

保证所有候选位置的坐标两两不同。

输出格式

输出一个数,表示最大利润。答案允许至多 10−610^{-6} 的相对或绝对误差。

准确地说,设你的输出为 aa,标准答案为 bb,当且仅当

∣a−b∣max⁡(1,∣b∣)≤10−6\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}

时,输出被接受。

原样例 1

2
1 1 1
3 3 1
1

原样例 2

3
4 5 5
4 6 7
1 3 8
10.1005050633883

原样例 3

2
0 0 1
1000000 1000000 1000000000
1000000000

精度说明

正确的误差要求为 10−610^{-6},具体判定公式见输出格式。