hdu 6127 Hard challing e

リンク
http://acm.hdu.edu.cn/showproblem.php?pid=6127
問題を解く
極の角を並べ替えて、2つのポインタをスキャンします。
コード

#include 
#define maxn 100010
#define eps 1e-8
using namespace std;
typedef long long ll;
ll s[maxn], n, ans;
const double pi=acos(-1);
struct point
{
    ll x, y, v;
    double th;
}pt[maxn];
ll read(ll x=0)
{
    ll c, f(1);
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(;isdigit(c);c=getchar())x=x*10+c-48;
    return f*x;
}
int main()
{
    ll T(read()), i, j;
    while(T--)
    {
        n=read();
        for(i=1;i<=n;i++)
        {
            pt[i].x=read(), pt[i].y=read(), pt[i].v=read();
            pt[i].th=atan2(pt[i].y,pt[i].x);
        }
        sort(pt+1,pt+n+1,[](point& p1, point& p2){return p1.th<p2.th;});
        for(i=1;i<=n;i++)pt[n+i]=pt[i], pt[n+i].th+=2*pi;
        for(i=1;i<=2*n;i++)s[i]=s[i-1]+pt[i].v;
        ans=0;
        for(i=j=1;i<=2*n;i++)
        {
            while(pt[i].th-pt[j].th>pi+eps)j++;
            auto v=s[i]-s[j-1];
            ans=max(ans,(s[n]-v)*v );
        }
        printf("%lld
",ans);
    }
    return 0;
}