题意：给出n个点，每个点有个权值，可以和任意另外一点构成线段，值为权值积。现问过原点的直线中交所有线段的权值和的最大值，注意直线必不经过点。
思路：直线可以将点集分为两侧，此时的权值为两侧点的乘积。而且由于是过原点的直线，所以不用暴力枚举两个点了...直接极角排序，这里我原先的极角排序有点小问题，最后还是找的别人的，以(0,x)为最小极角的。
然后前缀和权值以便分组求积。
枚举点，与原点相连作直线，然后以枚举点的对称点，二分找到最大的在它顺时针侧的点，然后注意要注意枚举点是否包含的两种情况，这样分成两部分求积即可。
/** @Date : 2017-08-16 13:18:05
* @FileName: 1008.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int ,int>
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5e4+20;
const double eps = 1e-6;
struct point
{
LL x, y, v;
point(){}
point(LL _x, LL _y, LL _v):x(_x),y(_y),v(_v){}
point(LL _x, LL _y):x(_x),y(_y){}
point operator -(const point &b) const
{
return point(x - b.x, y - b.y);
}
LL operator *(const point &b) const
{
return x * b.x + y * b.y;
}
LL operator ^(const point &b) const//少了个LL WA 3发
{
return x * b.y - y * b.x;
}
};
int sign(double x)
{
if(fabs(x) < eps)
return 0;
if(x < 0)
return -1;
else return 1;
}
LL xmult(point p1, point p2, point p0)
{
return (p1 - p0) ^ (p2 - p0);
}
LL distc(point a, point b)
{
return sqrt((double)((b - a) * (b - a)));
}
point p[N];
LL sum[N];
int cmp(point a, point b)//
{
int t = xmult(a, b, point(0, 0));
if(a.y * b.y <= 0)
{
if(a.y > 0 || b.y > 0)
return a.y < b.y;
if(a.y == 0 && b.y == 0)
return a.x < b.x;
}
return xmult(a, b, point(0,0)) > 0;
}
int cmp1(const point &a, const point &b) //以(x,0)为基准点(最小极角)
{
if (a.y == 0 && b.y == 0 && a.x*b.x <= 0)return a.x>b.x;
if (a.y == 0 && a.x >= 0 && b.y != 0)return true;
if (b.y == 0 && b.x >= 0 && a.y != 0)return false;
if (b.y*a.y <= 0)return a.y>b.y;
return xmult(a,b, point(0,0)) > 0 || (xmult(a,b,point(0,0)) == 0 && a.x < b.x);
}
int bina(int x, int l, int r)
{
int ans = -1;
point ops = point(-p[x].x, -p[x].y);
while(l <= r)
{
int mid = (l + r) >> 1;
if(cmp1(ops, p[mid]) != 1)
{
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
return ans;
}
int main()
{
int T;
cin >> T;
while(T--)
{
MMF(sum);
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
LL x, y, v;
scanf("%lld%lld%lld", &x, &y, &v);
p[i] = point(x, y, v);
}
sort(p + 1, p + n + 1, cmp1);
/*for(int i = 1; i <= n; i++)
printf("%lf %lf
", p[i].x, p[i].y);*/
LL ans = 0;
for(int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + p[i].v;
for(int i = 1; i <= n; i++)
{
if(p[i].y >= 0)
{
int r = bina(i, i + 1, n);
if(r == -1)
r = i;
LL res1 = (sum[n] - (sum[r] - sum[i - 1])) * (sum[r] - sum[i - 1]);
LL res2 = (sum[n] - (sum[r] - sum[i])) * (sum[r] - sum[i]);
ans = max(max(res1, res2), ans);
//cout << ans <<"r "<< r << endl;
}
else
{
int l = bina(i, 1, i);
if(l == -1)
l = 0;
LL res1 = (sum[n] - (sum[i] - sum[l])) * (sum[i] - sum[l]);
LL res2 = (sum[n] - (sum[i - 1] - sum[l])) * (sum[i - 1] - sum[l]);
ans = max(max(res1, res2), ans);
//cout <<i <<"~" << res1 << " l: " << l<<endl;
}
}
printf("%lld
", ans);
}
return 0;
}
/*
999
9
0 1 7
1 0 8
0 -1 9
-1 0 10
1 1 2
0 0 1
1 -1 4
-1 1 5
-1 -1 3
1.000000 0.000000
0.000000 0.000000
1.000000 1.000000
0.000000 1.000000
-1.000000 1.000000
-1.000000 0.000000
-1.000000 -1.000000
0.000000 -1.000000
1.000000 -1.000000
*/