HZNUOJ

Max Area

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:7     AC:3     Score:99.81

Description

又是这道题,请不要惊讶,也许你已经见过了,那就请你再来做一遍吧。这可是wolf最骄傲的题目哦。 在笛卡尔坐标系正半轴(x>=0,y>=0)上有n个点,给出了这些点的横坐标和纵坐标,但麻烦的是这些点的坐标没有配对好,你的任务就是将这n个点的横坐标和纵坐标配对好,使得这n个点与x轴围成的面积最大。

Input

在数据的第一行有一个正整数m,表示有m组测试实例。接下来有m行,每行表示一组测试实例。每行的第一个数n,表示给出了n个点,接着给出了n个x坐标和y坐标。(给出的x轴的数据不会重复,y轴数据也不会重复)(m<5000,1<n<50) 如: 2 4 x1 x2 x3 x4 y1 y2 y3 y4 5 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5

Output

输出所计算的最大面积,结果保留两位小数,每组数据占一行。

Samples

input
2 4 0 1 3 5 1 2 3 4 6 14 0 5 4 6 8 1 5 6 2 4 3
output
15.00 59.00

Author

ZJCM WL