hdu--6127--Hard challenge

绝地灬酷狼 2022-06-10 09:40 100阅读 0赞

# Hard challenge #

**Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)  
Total Submission(s): 572    Accepted Submission(s): 232**

Problem Description

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.

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×104).  
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

2
    2
    1 1 1
    1 -1 1
    3
    1 1 1
    1 -1 10
    -1 0 100

Sample Output

1
    1100

题意：

平面上有n个点，每个点有一个value值，每两个点之间都有一条线，这条线的value是两点的value之积，给出这些点的·坐标，并且这些直线不过原点，求过原点一条线，切割的线的value之和最大。

解题思路：

因为过原点的直线不过给出的任何一点，所以给出的点要么在直线的一侧，要么在另一侧。此时切割的线的value之和为左边各个点的权重和L，与右边的各个点的权重和R的乘积R\*L。

先求出各个点的斜率，根据斜率对他们进行排序，先让直线指向第一个点（看作枚举的这条直线偏向这个点右边一点进行处理），求出L 和R，ans=l\*R，再枚举直线指向其他已排好序点，按照同样的方法处理，并且更新ans=max（ans，L\*R），当把每个点都枚举一遍，答案就出来了。

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 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 
 68 
 69 
 70 
 71 
 72 
 73 
 74 
 75 
 76 
 77 
 78 
 79 
 80 
 81 
 82 
 83 
 84 
 85 
 86 
 87 
 88 
 89 
 90 
 91 
 92 
 93 
 94 
 95 
 96 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 #define&nbsp;maxn&nbsp; 
 50005 
 
 #define&nbsp;pi&nbsp; 
 4*atan( 
 1. 
 0) 
 
 #define&nbsp;ll&nbsp; 
 long&nbsp; 
 long 
 
 using&nbsp; 
 namespace&nbsp;std; 
 ll&nbsp;sum_L,&nbsp;sum_R; 
 
 int&nbsp;n; 
 
 struct&nbsp;Node 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x,&nbsp;y,&nbsp;v; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 double&nbsp;s; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 bool&nbsp;is_up; 
 ///值为1时，表示在x轴上方 }&nbsp;node[maxn]; 
 
 
 double&nbsp;get_s( 
 int&nbsp;x,&nbsp; 
 int&nbsp;y) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(x&nbsp;&lt;&nbsp; 
 0&nbsp;&amp;&amp;&nbsp;y&nbsp;&gt;&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;pi&nbsp;-&nbsp;atan(-( 
 double)y&nbsp;/&nbsp;( 
 double)x); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(x&nbsp;&gt;&nbsp; 
 0&nbsp;&amp;&amp;&nbsp;y&nbsp;&lt;&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;pi&nbsp;-&nbsp;atan(-( 
 double)y&nbsp;/&nbsp;( 
 double)x); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;atan(( 
 double)y&nbsp;/&nbsp;( 
 double)x); 
 } 
 
 double&nbsp;get_up( 
 int&nbsp;x,&nbsp; 
 int&nbsp;y) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(y&nbsp;&gt;&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp; 
 if(y&nbsp;&lt;&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(x&nbsp;&lt;&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 bool&nbsp;cmp(Node&nbsp;a,&nbsp;Node&nbsp;b) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;a.s&nbsp;&lt;&nbsp;b.s; 
 } 
 
 ll&nbsp;work() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;ans&nbsp;=&nbsp;sum_L&nbsp;*&nbsp;sum_R; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 double&nbsp;cur_s&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;i&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(node[i].s&nbsp;==&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(i&nbsp;&lt;=&nbsp;n) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cur_s&nbsp;=&nbsp;node[i].s; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while(node[i].s&nbsp;==&nbsp;cur_s) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(node[i].is_up&nbsp;==&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum_L&nbsp;-=&nbsp;node[i].v; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum_R&nbsp;+=&nbsp;node[i].v; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum_L&nbsp;+=&nbsp;node[i].v; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum_R&nbsp;-=&nbsp;node[i].v; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp;max(ans,&nbsp;sum_L&nbsp;*&nbsp;sum_R); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;ans; 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;T; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;T); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(T--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum_L&nbsp;=&nbsp;sum_R&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;n); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d%d%d",&nbsp;&amp;node[i].x,&nbsp;&amp;node[i].y,&nbsp;&amp;node[i].v); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node[i].s&nbsp;=&nbsp;get_s(node[i].x,&nbsp;node[i].y);&nbsp; 
 ///计算各个点的斜率 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node[i].is_up&nbsp;=&nbsp;get_up(node[i].x,&nbsp;node[i].y);&nbsp; 
 ///判断在x轴上方还是下方，枚举的第一条直线为x轴 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(node[i].is_up&nbsp;==&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum_L&nbsp;+=&nbsp;node[i].v; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum_R&nbsp;+=&nbsp;node[i].v; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sort(node&nbsp;+&nbsp; 
 1,&nbsp;node&nbsp;+&nbsp; 
 1&nbsp;+&nbsp;n,&nbsp;cmp);&nbsp; 
 ///根据斜率进行排序 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;ans&nbsp;=&nbsp;work(); 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%lld\n",&nbsp;ans); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>