2017 Multi-University Training Contest 7 hdu 6127

HDU - 6127

题意：平面直角坐标系上有n个整点，第i个点有一个点权val_i，坐标为(x​i​​,y​i​​)，其中不存在任意两点连成的直线经过原点。这些整点两两之间连有一条线段，线段的权值为其两端点的权值之积。你需要作一条过原点而不过任意一个给定整点的直线，使得和这条直线相交的线段的权值和最大。

思路：按每个点与x正半轴的夹角排序，枚举每一个点为中线将点分为2部分，再考虑当前点在左边或者右边的2中情况即可，由于是一个圆周（这里有坑），所以在排序后再接一圈就是了，不过接起来的时候由于每个点都是转了一圈，所以角度要加2*PI

AC代码：

#include "iostream"
#include "iomanip"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#pragma comment(linker, "/STACK:102400000,102400000")
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a,x) memset(a,x,sizeof(a))
#define step(x) fixed<< setprecision(x)<<
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define ll long long
#define endl ("
")
#define ft first
#define sd second
#define lrt (rt<<1)
#define rrt (rt<<1|1)
using namespace std;
const long long INF = 1e18+1LL;
const int inf = 1e9+1e8;
const int N=1e7+100;
const ll mod=1e9+7;
const double PI=acos(-1.0);

struct Point{
    ll x,y,v;
    double k;
    void rek(){
        if(x==0){
            if(y>0) k=PI/2.0;
            else k=2*PI-PI/2.0;
        }
        else{
            k=atan((1.0*y)/(1.0*x)); //cout<<k<<endl;
            if(x<0) k+=PI;
            if(k<0) k+=2*PI;
        }
    }
    bool friend operator< (Point a, Point b){
        return a.k<b.k;
    }
}p[100005];

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--){
        mem(p,0);
        int n; cin>>n;
        for(int i=1; i<=n; ++i){
            cin>>p[i].x>>p[i].y>>p[i].v;
            p[i].rek();
        }
        sort(p+1,p+1+n);
        for(int i=1; i<=n; ++i) p[i+n]=p[i],p[i+n].k+=2*PI; //排序后再接一圈
        ll L=0, R=0, e=2, ans=0; double K=p[1].k;  //e标记的是R这一边的第一个点的序号
        for(int i=2; i<=n; ++i){
            if(p[i].k>K && p[i].k<K+PI){
                L+=p[i].v;
                e=i+1;
            }
            else R+=p[i].v;
        }                   //bug(L) bug(R)
        ans=max(ans,(L+p[1].v)*R);
        ans=max(ans,L*(R+p[1].v));          //bug(ans)
        for(int i=2; i<=n; ++i){
            if(p[i].k > K && p[i].k < K+PI) L-=p[i].v;
            else R-=p[i].v;                       //cout<<R<<"UUU
";
            K=p[i].k; R+=p[i-1].v;                 //cout<<R<<"FFF
";
            for(int j=e; p[j].k>K && p[j].k<K+PI && j<=2*n; ++j){
                if(e!=i) L+=p[j].v; R-=p[j].v; e++;
            }                             //cout<<L<<" "<<R<<" "<<e<<endl;
            ans=max(ans,(L+p[i].v)*R);
            ans=max(ans,L*(R+p[i].v));
        }
        cout<<ans<<endl;
    }
    return 0;
}