equation

题目链接

题意

有数列$a$和$b$，计算有多少个$x$满足

$$\sum_{i=1}^{N} |a_{i} \times x +b_{i}| = C.$$

思路

若$a_{i} \times x + b_{i} > 0$，则有$x > - \frac{b_{i} }{a_{i}}$。
我们对这个式子排序然后不断变换$x$的范围看这个解是否合理。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
const int N = 1e3 + 5;
inline ll gcd(ll a, ll b)
{
    if (a < b)
        swap(a, b);
    while (b)
    {
        ll t = a;
        a = b;
        b = t % b;
    }
    return a;
}

struct frac
{
    ll a, b;
    bool operator < (const frac& x) const
    {
        return a * x.b < b * x.a;
    }
    bool operator > (const frac& x) const
    {
        return a * x.b > b * x.a;
    }
    inline bool operator == (const frac& x) const
    {
        return a == x.a && b == x.b;
    }
    inline bool operator != (const frac& x) const
    {
        return !(*this == x);
    }
    inline bool operator >= (const frac& x) const
    {
        return *this > x || *this == x;
    }
    inline bool operator <= (const frac& x) const
    {
        return *this < x || *this == x;
    }
    inline void pretty()
    {
        ll g = gcd(abs(a), abs(b));
        if (g)
            a /= g, b /= g;
        if (a * b < 0)
            a = -abs(a), b = abs(b);
        else if (a < 0 && b < 0)
            a = abs(a), b = abs(b);

    }
    frac(ll _a=0, ll _b=1)
    {
        a = _a, b = _b;
        pretty();
    }
    inline frac operator + (const frac& x) const
    {
        frac tmp = frac();
        tmp.a = a * x.b + x.a * b;
        tmp.b = b * x.b;
        tmp.pretty();
        return tmp;
    }
    inline frac operator - (const frac& x) const
    {
        frac tmp = frac();
        tmp.a = a * x.b - b * x.a;
        tmp.b = b * x.b;
        tmp.pretty();
        return tmp;
    }
    inline frac operator * (const frac& x) const
    {
        frac ret = frac();
        ret.a = a * x.a;
        ret.b = b * x.b;
        ret.pretty();
        return ret;
    }
    inline frac operator / (const frac& x) const
    {
        frac ret = frac();
        ret.a = a * x.b;
        ret.b = b * x.a;
        ret.pretty();
        return ret;
    }
    inline void print()
    {
        if (a == 0)
            printf("0/1");
//        else if (b == 1)
//            printf("%lld\n", a);
        else
            printf("%lld/%lld", a, b);
    }
};

struct node
{
    ll a, b;
    frac cmp;
    int id;
    bool operator < (const node& x) const
    {
        return cmp < x.cmp;
    }
}a[100005];
frac ans[200005];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, c;
        scanf("%d%d", &n, &c);
        ll sufa = 0, sufb = 0, prea = 0, preb = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld%lld", &a[i].a, &a[i].b);
            a[i].cmp = frac(-a[i].b, a[i].a);
            a[i].id = i;
            sufa += a[i].a;
            sufb += a[i].b;
        }
        sort(a + 1, a + n + 1);
        int m = 0, f = 0, no = 0;
        if (sufa != prea)
        {
            ll tmpa = prea - sufa;
            ll tmpb = c - (preb - sufb);
            ans[m++] = frac(tmpb, tmpa);
            if (ans[0] >= a[1].cmp)
                m--;
        }
        else
        {
            if (c == preb - sufb)
                f = 1;
            else
                no = 1;
        }
        /*
        for (int i = 1; i <= n; i++)
        {    dbg(i);a[i].cmp.print();}

        */
        for (int i = 1; i <= n; i++)
        {
        //    dbg(i, prea, sufa, preb, sufb);
            sufa -= a[i].a;
            sufb -= a[i].b;
            if (sufa != prea)
            {
                ans[m++] = frac(c - (preb - sufb), prea - sufa);
                if (ans[m - 1] != a[i].cmp)
                    m--;
            }
            else
            {
                if (c == preb - sufb)
                    ans[m++] = a[i].cmp;
            }
            
            prea += a[i].a;
            preb += a[i].b;
            //dbg(i, m);
            if (sufa != prea)
            {
                ans[m++] = frac(c - preb + sufb, prea - sufa);
                if (ans[m - 1] <= a[i].cmp || !(i == n || ans[m - 1] < a[i + 1].cmp))
                    m--;
            }
            else if (i < n && a[i].cmp != a[i + 1].cmp)
            {
                if (c == preb - sufb)
                    f = 1;
                else
                    no = 1;
                break;
            }
        }
        if (f == 1)
        {
            puts("-1");
            continue;
        }
        if (no)
            m = 0;
        printf("%d", m);
        sort(ans, ans + m);
        for (int i = 0; i < m; i++)
            putchar(' '), ans[i].print();
        putchar('\n');
    }
    return 0;
}