计算几何之小数表示最简分数

https://ac.nowcoder.com/acm/contest/7852/E
技巧：枚举分母找分子，然后用上取整和下去整判断，不断减小误差，增加精度。

#include<bits/stdc++.h>

using namespace std;

const int maxn=100005;
typedef double db;
const db eps=1e-12;

inline db readb()
{   
    int f=1;db x=0;char s=getchar();
    for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
    for( ;isdigit(s);x=x*10+s-48,s=getchar());
    if( s=='.' ) for( db l=0.1,s=getchar();isdigit(s);x=x+(s-48)*l,l/=10,s=getchar() );
    return x*f;
}
int sgn( double d ) { return (d>eps)-(d<-eps); }; // 精度判断 

struct node{
    db l,r;
    bool operator < ( const node &rhs )const{ return l<rhs.l; };
}p[maxn],tmp[maxn];

int n;

bool check( db x )
{
    db now=0;
    for( int i=1;i<=n;i++ )
    {
        if( p[i].r-x+eps<now ) return false;
        now=max(p[i].l,now)+x;
    }
    return true;
}



int main()
{
    n=readb();
    db mins=1000000;
    for( int i=1;i<=n;i++ )
    {
        p[i].l=readb(),p[i].r=readb();
        mins=min(mins,p[i].r-p[i].l);
    }
    sort(p+1,p+1+n);
    db ls=0,rs=mins;
    while( rs-ls>=eps )
    {
        db mid=(ls+rs)/2;
        if( check(mid) ) ls=mid;
        else rs=mid;
    }
    db ep=1.0;
    int mi=0,mu=0;
    for( int i=1;i<=100000;i++ )
    {
        if( sgn(ls*i - (db)ceil(ls*i))==0 )
        {
             mi=ceil(ls*i);
             mu=i;
             ep=fabs( ls*i - (db)ceil(ls*i) );
        }
        if( sgn(ls*i - (db)floor(ls*i))==0 )
        {
             mi=floor(ls*i);
             mu=i;
             ep=fabs( ls*i - (db)floor(ls*i) );
        }

    }
    cout<<mi<<"/"<<mu<<"\n";


}