HDU - 6627 equation

​ 解带很多绝对值的一次方程,计算每个绝对值的零点,枚举 $x$ 在哪两个相邻零点构成的区间内,就可以拆开绝对值,算出解后需要验证是否合法。比赛时候写的很丑(

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5;
int T, N, C;
const double eps = 1e-8;

struct node {
    double p;
    long long a, b;

    explicit node(long long a = 0, long long b = 0, double p = 0.0) : a(a), b(b), p(p) {}

    bool operator<(const node &x) const { return p < x.p; }

    bool operator==(const node &x) const {
        return fabs(p - x.p) < eps && a == x.a && b == x.b;
    }
} in[maxn], pre[maxn], suf[maxn];

vector<node> ans;

int inline sgg(double x) {
    return (x > eps) - (x < -eps);
}

int main() {
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d", &N, &C);
        for (int i = 1; i <= N; i++)
            scanf("%lld %lld", &in[i].a, &in[i].b);
        for (int i = 1; i <= N; i++)
            in[i].p = -1.0 * (double) in[i].b / (double) in[i].a;
        sort(in + 1, in + N + 1);
        pre[0].a = pre[0].b = 0;
        for (int i = 1; i <= N; i++)
            pre[i].a = pre[i - 1].a + in[i].a, pre[i].b = pre[i - 1].b + in[i].b;
        suf[N + 1].a = suf[N + 1].b = 0;
        for (int i = N; i; i--)
            suf[i].a = suf[i + 1].a - in[i].a, suf[i].b = suf[i + 1].b - in[i].b;
        bool infans = false;
        ans.clear();
        in[0].p = -999999999999999.0;
        in[N + 1].p = 999999999999999.0;
        for (int i = 0; i <= N; i++)
        {
            long long A = pre[i].a + suf[i + 1].a;
            long long B = pre[i].b + suf[i + 1].b;
            B = (long long) C - B;
            if (A == 0)
            {
                if (B == 0)
                {
                    if (sgg(in[i].p - in[i + 1].p) == 0)
                    {
                        A = in[i].a;
                        B = in[i].b;
                        long long sgn = 1;
                        if (A > 0 && B < 0 || A < 0 && B > 0)
                            sgn = -1;
                        if (A < 0)
                            A = -A;
                        if (B < 0)
                            B = -B;
                        long long g = __gcd(A, B);
                        if (g)
                            A /= g, B /= g;
                        if (B == 0)
                            A = 1, sgn = 1;
                        ans.emplace_back(-1 * sgn * B, A, in[i].p);
                    }
                    else
                    {
                        infans = true;
                        break;
                    }
                }
                continue;
            }
            long long sgn = 1;
            if (A > 0 && B < 0 || A < 0 && B > 0)
                sgn = -1;
            if (A < 0)
                A = -A;
            if (B < 0)
                B = -B;
            long long g = __gcd(A, B);
            A /= g, B /= g;
            swap(A, B);
            if (A == 0)
                B = 1, sgn = 1;
            double p = (double) sgn * A / B;
            if (sgg(p - in[i].p) >= 0 && sgg(p - in[i + 1].p) <= 0)
                ans.emplace_back(sgn * A, B, p);
        }
        if (infans)
        {
            puts("-1");
            continue;
        }
        sort(ans.begin(), ans.end());
        auto end = unique(ans.begin(), ans.end());
        ans.erase(end, ans.end());
        printf("%d", ans.size());
        for (auto i : ans)
            printf(" %lld/%lld", i.a, i.b);
        puts("");
    }
}