UVA 1616 Caravan Robbers 商队*者（二分）

x越大越难满足条件，二分，每次贪心的选区间判断是否合法。此题精度要求很高需要用long double，结果要输出分数，那么就枚举一下分母，然后求出分子，在判断一下和原来的数的误差。

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int maxn = 1e5+5;
const ld eps = 1e-11;
struct Seg
{
    int l,r;
    bool operator < (const Seg& x) const {
        return l<x.l || (l == x.l && r < x.r);
    }
}S[maxn];
#define bug(x) cout<<#x<<'='<<x<<endl
#define Pld(x) printf("%Lf
",x)
int n;

bool P(ld x)
{
 //   Pld(x);
    ld cur = 0;
    for(int i = 0; i < n; i++){
        cur = max(cur,(ld)S[i].l);
        cur += x;
        if(cur-S[i].r>eps) return false;

    }
    return true;
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d",&n)){
        for(int i = 0; i < n; i++){
            scanf("%d%d",&S[i].l,&S[i].r);
        }
        sort(S,S+n);
        ld L,R,mid;
        for(L = 0,R = S[n-1].r; R-L>eps; P(mid)?L=mid:R=mid)mid = (L+R)/2;

        int p,q;
        for(q = 1; q <= n+1; q++){
            p = round(L*q);
            ld t = (ld)p/q;
            if(fabs(t-L)<eps) { break;}
        }
        printf("%d/%d
",p,q);
    }
    return 0;
}