问题 E: The more the better

问题 E: The more the better

时间限制: 1 Sec  内存限制: 128 MB
提交: 83  解决: 29
[状态] [讨论版] [提交] [命题人:]
题目描述

    小g是名聪明的女Acmer,今天、很不幸的、很惨绝人寰的,小g的头被门重重的挤了一下,然后她晕了过去。。。好了暂且不说这坑爹的、不科学的、不懂得怜香惜玉的门。小g做了个梦。
    她梦到自己来到了一个王国、并且她的身份是一名学高八斗、才富五车、倾国倾城的学者。由于她实在是太聪明貌美了、以至于惊动了国王,于是她受到了国王的隆重接见。在接见上、国王出了一道题来考验她,国王说:


正题(我是隐身的两个字):
    我这里有一个二维平面,上面有n个点、n不小于9、不大于11,要求你从里面选出6个点、每个点不得重复使用,用它们构成两个三角形。
    那么这两个三角形的面积和Sum_area最大是多少?

    如果你答对了、那么我便奖赏你面积这么大的土地;
    如果你答错了、那么。。。那么就准备做人家的皇后吧^_^~


    小g:“。。。。。。”
    当听到最后一句的话的时候、原本淡定自若的小g差点儿又晕过去。原本对小g而言是道easy的不能再easy的题了,但是国王的最后一句话太有杀伤力了、一直在小g脑海中浮现、以至于小g不能集中心神囧~。

    为了不落入魔爪,小g用了一种不科学的通讯方式联系到了你、请求你的帮助。那么现在、聪明的你,能否帮助小g脱离国王的魔爪呢?


注意:
    当然,国王毕竟是一国之君,不会故意刁难我们的学者,所以为了降低难度:
    三角形面积可以为0;
    每个点最多只能使用一次;
    不必考虑三角形面积重叠所带来的问题,既Sum_area = area_a + area_b ,不必减去重叠部分。


输入

    输入数据有多组,第一行一个T,表示有T组测试。
    每组测试第一行一个整数n(9<=n<=11)。然后n行、表示n个不同的点,每行两个整数x、y表示柱子的坐标(0<=x、y<=100)。

输出

    对于每组测试,输出一个实数、既最大面积和,输出保留两位小数。

样例输入 Copy
1
9
13 21
84 60
24 82
41 53
30 45
62 10
25 58
6 59
27 5
样例输出 Copy
3671.50