题目链接
题意：二维平面上有n个点（没有重叠，都不在原点，任意两点连线不过原点），每个点有一个权值，用一条过原点的直线把他们划分成两部分，使两部分的权值和的乘积最大。输出最大的乘积。
极角排序后，将原来(-pi,pi]区间的元素copy到(pi,3pi]，用双指针维护一个角度差不超过pi的区间，记区间的权值和为sum1，用sum1*(sum-sum)更新ans
#include<bits/stdc++.h> using namespace std; typedef long long LL;const long double pi=3.14159265358979323846264338327950288L; const long double eps=1e-15;struct point {int x,y;LL val;long double j;bool operator <(const point rhs){return j<rhs.j;} }p[100005];int n; LL s[100005];LL sum(int l,int r) { // if(l>r) puts("========================");return s[r]-s[l]+p[l].val; }int main() {int T;scanf("%d",&T);while(T--){memset(s,0,sizeof(s));LL ans=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d%lld",&p[i].x,&p[i].y,&p[i].val);p[i].j=atan2l(p[i].y,p[i].x);}sort(p,p+n);for(int i=0;i<n;i++) p[i+n]=p[i],p[i+n].j+=2*pi;s[0]=p[0].val;for(int i=1;i<2*n;i++) s[i]=s[i-1]+p[i].val;for(int l=0,r=0;l<n;l++) //使用双指针 l,r {while(p[r+1].j<p[l].j+pi) r++;LL v1=sum(l,r);LL v2=s[n-1]-v1;ans=max(ans,v1*v2);}printf("%lld\n",ans);} }
