[POI1999][SPOJ 199]空心长方体

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file emptycuboids.in Output file emptycuboids.out

【题目描述】

在一个三维正坐标系中,存在N(N<=5000)个点,现在要求一点P(x,y,z),使得O(0,0,0)与P(x,y,z)两个顶点构成的长方体内不包括N个点中的任何一个点(在长方体边缘不算包括),并使这个长方体的体积最大。x,y,z均不得超过1000000。

【输入格式】

第一行有一个整数N。

接下来N行每行有三个整数,代表第i个点的x,y,z坐标。

【输出格式】

输出一行一个整数,即最大的体积。

【样例输入】

4

3 3 300000

2 200000 5

90000 3 2000

2 2 1000

【样例输出】

200000000000000

【提示】

对于样例,可取P(1000000,200000,1000)

【来源】

POI 1999 stage 1 Empty Cuboids

SPOJ 199 Empty Cuboids