该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
令人遗憾的是,L是直角。
题目描述
野豌豆非常喜欢钝角,他常常喜欢数平面上任选三个点能否组成钝角三角形,而每当野豌豆发现一个从未发现过的钝角三角形的时候,他就会获得这个三角形面积两倍的满意值。
现在给定二维平面内的n个点(xi,yi),请问野豌豆最多可以获得多少满意值。
输入格式
输入第一行仅包含一个正整数T(1≤T≤1000),表示数据组数。
对于每组测试数据,第一行包含一个正整数n(3≤n≤1000)表示平面上总共有n个点。
第i+1行包含两个正整数(xi,yi),表示第i个点的坐标,保证1≤xi,yi≤10000,且对于1≤i,j≤n,i=j,保证(xi,yi)=(xj,yj)。
输出格式
对于每组测试数据,输出一行一个正整数S,为野豌豆最多可以获得的满意值。
样例
3
4
5 7
9 8
2 10
4 2
6
6 8
4 9
9 10
8 2
3 8
9 4
10
3 3
2 4
1 2
6 4
9 2
8 9
4 4
6 3
7 7
9 4
52
145
660
数据范围
对于30%的数据,有3≤n≤300,且∑n≤600。
对于另外30%的数据,保证任意三点不共线。
对于100%的数据,1≤T≤1000,3≤n≤103,3≤∑n≤2×103,1≤xi,yi≤104,且保证任意两点不相等。保证答案一定为整数。
提示
对于样例中第一组数据中四个点的坐标如图所示,其中△ABC,△ABD,△ACD为钝角三角形,而△BCD为锐角三角形。
又因为S△ABC=7.5,S△ABD=9.5,S△ACD=9, 最后野豌豆可以获得的满意值等于S=2S△ABC+2S△ABD+2S△ACD=52。