2019杭电多校Contest5 1004 equation

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6627

题意是给出n个套上绝对值的一元一次方程，求x使得他们的和等于c。

对于|ax+b|，考虑去掉绝对值，只有两种情况 ax+b 和 -ax-b，取决于x的取值，也就是 x 与 b/a 的大小关系。

然后n个方程就会把x的范围划分为n+1个区间，然后当x取不同的范围，去掉绝对值的方程就会发生变化，一共有n+1种情况。

想着按照 -a/b 排一下序，这样x取每一个区间，对应不同的n+1个一元一次方程，直接求解然后判断是否在要求的区间范围内即可。

注意一下判断的时候一些细节。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+5;
const ll mod=998244353;
ll c;
int n;
struct node
{
    ll a,b;
};
bool cmp(node x,node y)
{
    return x.a*y.b<x.b*y.a;
}
bool cmp2(node x,node y)
{
    return x.a*y.b==x.b*y.a;
}
node f[N];
node ans[N];
int k;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof f);
        k=0;
        scanf("%d%lld",&n,&c);
        ll suma=0,sumb=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&f[i].a,&f[i].b);
            if(f[i].a<0)
            {
                suma+=f[i].a;
                sumb+=f[i].b;
            }
            else
            {
                suma-=f[i].a;
                sumb-=f[i].b;
            }
        }//cout<<suma<<" "<<sumb<<endl;
        sort(f+1,f+1+n,cmp);
        int ff=0;
        for(int i=0;i<=n;i++)
        {
            suma+=2*f[i].a;
            sumb+=2*f[i].b;
            if(suma==0&&sumb==c)
            {
                ff=1;
                break;
            }
            ll x=c-sumb;
            ll y=suma;
            if(y<0)
            {
                y*=-1;
                x*=-1;
            }
            ll g=__gcd(abs(x),y);
            if((x*f[i+1].a<=-f[i+1].b*y)&&(f[i].a*x>=-f[i].b*y))
                ans[++k]={x/g,y/g};
        }
        if(ff)
        {
            printf("-1
");
            continue;
        }
        k=unique(ans+1,ans+1+k,cmp2)-ans-1;
        printf("%d",k);
        for(int i=1;i<=k;i++)
        {
            printf(" %lld/%lld",ans[i].a,ans[i].b);
        }puts("");
    }
    return 0;
}