#P18502. Huge Oil Platform
Huge Oil Platform
Huge Oil Platform
Jeroen 计划在北海建造一座石油平台。他已经找到 个能够开采石油的位置,并估计了平台能够开采每个位置时所获得的收益。由于平台十分巨大,可以把这些开采位置视为平面上的点;在本题中,地球可以看作平面。
按照规定,平台必须是一个矩形,其方向可以任意旋转。平台本体很便宜,但其四周的安全围栏非常昂贵,因此建造费用等于这个矩形的周长。
位于矩形内部或边界上的所有位置都可以开采,收益为这些位置的收益之和。允许建造宽度和/或高度为 的退化矩形:一个单点的周长为 ,长度为 的退化线段矩形的周长为 。
求能够获得的最大利润,即开采收益总和减去平台建造费用。
输入格式
第一行包含一个整数 (),表示候选开采位置数。
接下来 行,每行三个整数 (,),表示一个位置的坐标及开采收益。
保证所有候选位置的坐标两两不同。
输出格式
输出一个数,表示最大利润。答案允许至多 的相对或绝对误差。
准确地说,设你的输出为 ,标准答案为 ,当且仅当
时,输出被接受。
原样例 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
精度说明
正确的误差要求为 ,具体判定公式见输出格式。