HDU 6627 equation（模拟，分类讨论）

冷不防 2021-11-08 15:56 266阅读 0赞

## 题意：给你n个ai和bi，给你C，求解方程：   ![在这里插入图片描述][20190805211701115.png]   分析：初中数学，分类讨论破除绝对值符号。每两个零点之间的区域都对应一个一元一次方程，把这些零点排序之后可以很容易得到每个区间的方程，每个区间都解一个一元一次方程，然后判断解是否在这个区间内。要特判a=0的情况，注意代码细节（写的很搓 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5+5;
    const double eps = 1e-8;
    int t,n,c;
    
    struct nd {
        int a,b,fz,fm;
    }p[N];
    
    bool cmp(nd x,nd y) {
        return (1.0*x.fz/x.fm<1.0*y.fz/y.fm);
    }
    
    int main() {
        scanf("%d",&t);
        while(t--) {
            map<pair<int,int>,int> mp;
            mp.clear();
            scanf("%d%d",&n,&c);
            int A=0,B=0;
            p[0].a=1,p[0].b=1e9;
            for(int i=1;i<=n;i++) {
                scanf("%d%d",&p[i].a,&p[i].b);
                A+=p[i].a,B+=p[i].b;
                int gd=__gcd(p[i].a,p[i].b);
                p[i].fz=-p[i].b/gd;
                p[i].fm=p[i].a/gd;
            }
            sort(p+1,p+1+n,cmp);
            int aa=-A,bb=-B,f=0,s=0;
            vector<int> s1,s2;
            for(int i=1;i<=n;i++) {
                if(aa==0) {
                    if(bb==c) {
                        f=1;break;
                    }else {
                        aa+=2*p[i].a,bb+=2*p[i].b;
                        continue;
                    }
                }else {
                    double x=1.0*(c-bb)/aa;
                    if( -p[i-1].b*1.0/p[i-1].a<=x && x<=-p[i].b*1.0/p[i].a) {
                        int gd = __gcd(c-bb,aa);
                        int tp=c-bb;
                        tp=tp/gd;
                        int tp2=aa/gd;
                        if((tp<0)+(tp2<0)==1) tp=-abs(tp);
                        else tp=abs(tp);
                        tp2=abs(tp2);
                        if(mp[{tp,tp2}]) {
                            aa+=2*p[i].a,bb+=2*p[i].b;
                            continue;
                        }
                        mp[{tp,tp2}]++;
                        s1.push_back(tp);
                        s2.push_back(tp2);
                        s++;
                    }
                }
                aa+=2*p[i].a,bb+=2*p[i].b;
            }
            double x=1.0*(c-bb)/aa;
            if( -1.0*p[n].b/p[n].a<=x) {
                int gd = __gcd(c-bb,aa);
                int tp=c-bb;
                tp=tp/gd;
                int tp2=aa/gd;
                if((tp<0)+(tp2<0)==1) tp=-abs(tp);
                else tp=abs(tp);
                tp2=abs(tp2);
                if(!mp[{tp,tp2}]) {
                    mp[{tp,tp2}]++;
                    s1.push_back(tp);
                    s2.push_back(tp2);
                    s++;
                }
            }
            if(f) printf("-1\n");
            else {
                printf("%d",s);
                for(int i=0;i<s;i++)
                    printf(" %d/%d",s1[i],s2[i]);
                printf("\n");
            }
        }
        return 0;
    }

[20190805211701115.png]: /images/20211108/fa08094480ce408db01eaccc2946d7f9.png