【极角排序】【扫描线】hdu6127 Hard challenge

平面上n个点，每个点带权，任意两点间都有连线，连线的权值为两端点权值之积。没有两点连线过原点。让你画一条过原点直线，把平面分成两部分，使得直线穿过的连线的权值和最大。

就把点极角排序后，扫过去，一侧的点会跨过直线与另一侧的所有点形成连线。此时的答案为两侧的权值和之积，尝试用此更新最终答案。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct Point{
	ll x,y,val;
	int xx;
	Point(const ll &x,const ll &y){
		this->x=x;
		this->y=y;
	}
	Point(const ll &x,const ll &y,const ll &xx){
		this->x=x;
		this->y=y;
		this->xx=xx;
	}
	Point(){}
	void read(){
		scanf("%lld%lld%lld",&x,&y,&val);
		if(x>0 && y>=0){
			xx=1;
		}
		else if(x<=0 && y>0){
			xx=2;
		}
		else if(x<0 && y<=0){
			xx=3;
		}
		else{
			xx=4;
		}
	}
}p[100005];
bool operator < (const Point &a,const Point &b){
	return a.xx!=b.xx ? a.xx<b.xx : a.x*b.y-a.y*b.x>0;
}
ll sum[100005];
int n,T;
int main(){
	scanf("%d",&T);
	for(;T;--T){
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			p[i].read();
		}
		sort(p+1,p+n+1);
		for(int i=n+1;i<=2*n;++i){
			p[i]=p[i-n];
			p[i].xx=p[i-n].xx+4;
		}
		sum[1]=p[1].val;
		for(int i=2;i<=n*2;++i){
			sum[i]=p[i].val+sum[i-1];
		}
		ll ans=0;
		int i;
		for(i=1;i<=n;++i){
			Point *pt=upper_bound(p+1,p+n*2+1,Point(-p[i].x,-p[i].y,p[i].xx+2));
			ans=max(ans,(sum[pt-p-1]-sum[i-1])*(sum[n]-sum[pt-p-1]+sum[i-1]));
		}
		printf("%lld
",ans);
	}
	return 0;
}