【Link】:http://acm.hdu.edu.cn/showproblem.php?pid=6127

【Description】



平面上有n个点,每个点有一个价值，每两个点之间都有一条线段，定义线段的值为两个点价值的乘积，现在让你找一条过原点的直线(直线不经过任何一个节点)，将这条直线所经过的所有线段的值求和，问最大的和是多少.

【Solution】



假设有一条线把x轴上方和x轴下方的点分开了;

这样这条线的答案就为(val上1+val上2+…+val上n)*(val下1+val下2+…+val下n);

把上边的点的权值加起来,下边的点的权值也加起来.然后做下乘法就好.

之后,我们只要一点一点地逆时针旋转这条直线就好了;

每次遇到的第一个点,就改变上半部分删掉它之后权值的改变量;

在所有里面取最大值即可;

在转的时候,不管是直线的哪一个地方,只要遇到了一个点就停下来;

然后计算改变量.

如果是在x轴的下方的点的话,就是从直线的下方变成上方.

如果是在x轴的上方…

遇到的是哪一点并不好判断!

于是,我们考虑把x轴下方的点按原点对称到上方来.

(记录它原来是下方的);

这样,我们只要按照角升序排一下.

然后顺序处理,就能知道下一个会遇到的点是哪一个点了.

因为不存在两点经过原点,所以不会出现重复点.

虽然我们把它翻到了x轴上方,但我们在处理的时候,还是在原图上基础上处理的,即每个点转到之后和直线的位置关系

只不过能更清楚的知道下一个遇到的点是什么



【NumberOf WA】



0



【Reviw】



老是重新算很麻烦,就尝试一步一步地改变.



【Code】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define ri(x) scanf("%d",&x)

#define rl(x) scanf("%lld",&x)

#define rs(x) scanf("%s",x+1)

#define oi(x) printf("%d",x)

#define ol(x) printf("%lld",x)

#define oc putchar(' ')

#define os(x) printf(x)

#define all(x) x.begin(),x.end()

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 5e4;

struct abc{

    LL x,y,val;

    int tag;

    double c;

    friend bool operator < (const abc &a,const abc &b){

        return a.c > b.c;

    }

};

int n;

abc a[N+10];

LL sqr(LL x){

    return x*x;

}

int main(){

    //Open();

    //Close();

    int T;

    ri(T);

    while (T--){

        ri(n);

        rep1(i,1,n){

            rl(a[i].x),rl(a[i].y),rl(a[i].val);

            if (a[i].y < 0){

                a[i].tag = 0;

                a[i].x = - a[i].x;

                a[i].y = - a[i].y;

            }else

                a[i].tag = 1;

            a[i].c = 1.0*a[i].x/(1.0*sqrt((double)(sqr(a[i].x)+sqr(a[i].y))));

        }

        sort(a+1,a+1+n);

        LL s0 = 0,s1 = 0,temp = 0,ans;

        rep1(i,1,n){

            if (a[i].tag==0)

                s0 += a[i].val;

            else

                s1 += a[i].val;

        }

        rep1(i,1,n)

            if (a[i].tag == 1)

                temp += s0*a[i].val;

        ans = temp;

        rep1(i,1,n){

            if (a[i].tag == 1){

                temp = temp - a[i].val*s0 + a[i].val*(s1-a[i].val);

                s1 -= a[i].val;

                s0 += a[i].val;

            }else{

                temp = temp - a[i].val*s1 + a[i].val*(s0-a[i].val);

                s1 += a[i].val;

                s0 -= a[i].val;

            }

            ans = max(ans,temp);

        }

        ol(ans);puts("");

    }

    return 0;

}