hdu6127 (多校联合第七场) 几何 枚举

                                      HDU 6127

题目大意：

给出N个点的坐标，和每个点的一个值（记为val）。任意两个点构成的线段的价值为这两个点各自的val乘积。

现在让你求出一条过原点的直线，使得这条直线通过的所有线段价值和最大（题目保证任意给出的两个点组成的直线不会通过原点）。

大致思路：

我们知道一条直线会将一个平面分成两部分（假设为A平面和B平面），那么所有的点就会分成两种，一种在A平面，一种在B平面。我们分别求出分布在A平面的点的val总和ans1和分布在B平面的点的val总和ans2，那么这条直线通过所有的线段价值和为ans1*ans2（相当于(a+b+c)*(a1+b1+c1)=a*a1+a*b1+a*c1+b*a1+b*b1+b*c1+c*a1+c*b1+c*c1）。

我们要寻找一条分割线，使得分割后的A平面的ans1乘上B平面的ans2最大。

如图所示，假设现在有6个点（1,2,3,4,5,6）。

我们可以看出x=0这条直线就将所有的点分成两部分了（A平面为x<0,B平面为x>0)。

定义变量sum为我们最终求得的结果。那么sum的初始值就为（val6+val5+val4）*（val1+val2+val3）(看图)。

我们现在就要找下一条分割线了，但是从那里找呢？

就像图上一样，我们可以把点1到原点的线段（假设为直线y1）当成下一条分割线，然后进行计算。 当选点1时，我们可以想象此时这条分割线为y1向右旋转了一丢丢。那么点1就跑到A平面去了，而B平面就没了点1。所以此时sum=

max(sum，(ans1+val1)*(ans2-val2))；然后按照这个方法我们再找下一条分割线。。。

但是再选的话是选 点2还是点6呢？ 如果我们不按照某种“顺序”依次找分割线的话，A平面会多或者少计算某些点，B平面也一样。。。

所以重要的来了。。我们可以将所有的点与原点构成的直线的斜率（也可以理解为极角）依次求出来，然后进行排序。当我们找分割线的时候，就依次从最大（最小）的斜率开始找(看图，其实就是要将可选的分割线进行转圈筛选)。然后每次算，每次维护sum，那么结果就是我们要求的。

代码如下：

#include
#include
#include
#include
#define ll long long
#define eps 1e-8
using namespace std;
struct Point
{int x;int y;int val;double jiao;
} point[200005];
bool cmp(Point a,Point b)
{return a.jiao>b.jiao;
}
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);ll lsum=0,rsum=0;for(int i=0; i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！