Hard challenge
time limit per test 2 second memory limit per test 256 megabytes
There are n points on the plane, and the ith points has a value vali, and its coordinate is (xi,yi). It is guaranteed that no two points have the same coordinate, and no two points makes the line which passes them also passes the origin point. For every two points, there is a segment connecting them, and the segment has a value which equals the product of the values of the two points. Now HazelFan want to draw a line throgh the origin point but not through any given points, and he define the score is the sum of the values of all segments that the line crosses. Please tell him the maximum score.

传送门:HDU6127

Input

The first line contains a positive integer T(1≤T≤5), denoting the number of test cases. For each test case: The first line contains a positive integer n(1≤n≤5×1e4). The next n lines, the ith line contains three integers xi,yi,vali(|xi|,|yi|≤109,1≤vali≤104).

Output

For each test case: A single line contains a nonnegative integer, denoting the answer.

Sample Input

1
2
3
4
5
6
7
8
2
2
1 1 1
1 -1 1
3
1 1 1
1 -1 10
-1 0 100

Sample Output

1
2
1
1100

题解

转化为一条直线将所有点分成两块,答案是两块的点的和乘起来 然后取最大的 考虑按atan排序 这样初始我们把线定为y轴然后逆时针转动 碰到的肯定是离的最近的一个点 然后维护答案

极角排序

AC code:(不包含输入类)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.io.*;  
import java.util.*;
public class Main {
static double pai = 3.141592653589;
static double eps = 1e-6;
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
while(sc.hasNext()){
int n=sc.nextInt();
Point[]p=new Point[n];
long sum1=0;
long sum2=0;
for(int i=0;i<n;i++){
int x=sc.nextInt();
int y=sc.nextInt();
int v=sc.nextInt();
p[i]=new Point(x,y,v);
if(x>=0)sum1+=v;
else sum2+=v;
}
Arrays.sort(p,0,n);
long res=sum1*sum2; //初始时按y轴划一条线, sum1是y轴右边的和 sum2是y轴左边的和
for(int i=0;i<n;i++){
if(p[i].x>=0){
sum1-=p[i].v;
sum2+=p[i].v;
}else{
sum1+=p[i].v;
sum2-=p[i].v;
}
res=Math.max(res, sum1*sum2);
}
pw.println(res);
pw.flush();
}

}

}
class Point implements Comparable<Point>{
static double eps = 1e-6;
static double pai = 3.141592653589;
int x;
int y;
double angle;
long v;
Point(int x,int y,long v){
this.x=x;
this.y=y;
this.v=v;
if(x==0)this.angle=pai/2;
else this.angle=Math.atan(this.y*1.0/this.x); //atan
}
@Override
public int compareTo(Point o) {
double t1=this.angle; //atan排序
double t2=o.angle;
/*double t1=Math.atan2(this.y,this.x);
double t2=Math.atan2(o.y,o.x);*/
if(Math.abs(t1-t2)<eps)return 0;
else if(t1<t2)return -1;
else if(t1>t2)return 1;
return 0;
}
}