hdu 6127 Hard challenge

Problem

acm.hdu.edu.cn/showproblem.php?pid=6127

Meaning

平面上有 n 个不重合的点，任意三点不共线，任意两点所在直线不经原点。
每个点有个 value，任意两个点连出的线段的 value 是该两点 value 的乘积。
现从原点引出一条直线，要不经过任意给出的点，每穿过一条线段，就得到这条线段的 value。问能取得的最大的 value。

Analysis

对所有的点按角度排序（极角排序，或按斜率排），n 个点被直线分隔在两个半平面内，记其中一半的总 value 为 L，另一半的为 R，则候选解为 L * R。
枚举直线的斜率，每扫过一个点，就把它从原来的那一半中去除，而加到另一半中，更新答案。
（我是用斜率排序，枚举斜率时只枚举 180∘ ，用了一个特殊点判断扫描结束。去掉这个判断也能过）

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 50000;

struct point
{
    long long x, y, v;
    // 按斜率升序排
    bool operator < (const point &rhs) const
    {
        // 如果点在 y 轴左边
        // 要临时把它关于原点对称到 y 轴右边
        long long ax = x, ay = y, bx = rhs.x, by = rhs.y;

        if(x < 0)
            ax = -x, ay = -y;

        if(rhs.x < 0)
            bx = -rhs.x, by = -rhs.y;

        return ay * bx < by * ax;
    }
} p[N], terminal;

int main()
{
    // terminal 是一个在 y 轴正半轴上的点
    terminal.x = 0;
    terminal.y = 1;
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%I64d%I64d%I64d", &p[i].x, &p[i].y, &p[i].v);
        sort(p, p + n);

        long long L = 0, R = 0;
        // 初始时按 y 轴来分点
        // y 轴左边的算入 L
        // y 轴右边的算入 R
        // y 轴上的，正半轴算 L，负半轴算 R（因为逆时针扫）
        for(int i = 0; i < n; ++i)
            if(p[i].x < 0)
                L += p[i].v;
            else if(p[i].x > 0)
                R += p[i].v;
            else if(p[i].y > 0)
                L += p[i].v;
            else
                R += p[i].v;

        long long ans = L * R;
        // 枚举扫过的点
        for(int i = 0; i < n; ++i)
        {
            if(p[i].x < 0)
            {
                L -= p[i].v;
                R += p[i].v;
            }
            else if(p[i].x > 0)
            {
                L += p[i].v;
                R -= p[i].v;
            }
            else if(p[i].y > 0)
            {
                L -= p[i].v;
                R += p[i].v;
            }
            else
            {
                L += p[i].v;
                R -= p[i].v;
            }
            ans = max(ans, L * R);
            // 如果超过了 terminal 点
            // 则扫描结束
            // （去掉也能过）
            if(terminal < p[i])
                break;
            else if(!(p[i] < terminal))
                break;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}