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

成绩 开启时间 2014年09月19日 星期五 10:08
折扣 0.8 折扣时间 2014年09月26日 星期五 10:08
允许迟交 是 关闭时间 2014年09月26日 星期五 10:08
输入文件 emptycuboids.in 输出文件 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