UVA - 1616 Caravan Robbers 二分＋暴力轉換

UVA - 1616 Caravan Robbers 二分＋暴力轉換

題目大意：給出n條線段，把每條線段變成原來線段的一條子線段，使得改變後的所有線段等長且不相交，輸出最大長度

解題思路：這題要用long double確保精度，精度要求很高，接下來就是將這個long double的數轉化為兩個整數相除的結果了，有兩種方法，學習到了

#include
#include
#include
using namespace std;
#define maxn 100010
#define esp 1e-11

struct Line{
    int L, R;
}line[maxn];
int n;

bool ok(long double len) {
    long double cur = 0.0, t;
    for(int i = 0; i < n; i++) {
        t = line[i].L * 1.0;
        cur = max(t, cur);
        if(cur + len - line[i].R > esp)
            return false;
        cur += len;
    }
    return true;
}

bool cmp(const Line a, const Line b) {
    if(a.L == b.L)  
        return a.R < b.R;
    return a.L < b.L;
}

int main() {

    while(scanf("%d", &n) != EOF) {
        for(int i = 0; i < n; i++)
            scanf("%d%d", &line[i].L, &line[i].R);
        sort(line, line + n, cmp);
        long double L = 0.0, R = line[n - 1].R + esp;
        while(R - L > esp) {
            long double mid = (L + R) / 2;
            if(ok(mid)) 
                L = mid;
            else
                R = mid;
        }
        /*
           int i;
           for(i = 1; i <= n + 1; i++) {
           int p = (int)(L * i + 0.5);
           long double t = p * 1.0 / i;
           if(t - L < 2 * esp && L - t < esp * 2)
           break;       
           }
           printf("%d/%d\n", (int)(L * i + 0.5), i);
        */
        long double Min = 0x3f3f3f3f;
        int p, q;
        for(int i = 1; i <= maxn; i++) {
            int j = floor(L * i);
            if(fabs((long double)(j) / i - L) < Min) {
                p = j;
                q = i;
                Min = fabs((long double)(j) / i - L);
            }

            j = ceil(L * i);
            if(fabs((long double)(j) / i - L) < Min)    {
                p = j;
                q = i;
                Min = fabs((long double)(j) / i - L);
            }
        }
        printf("%d/%d\n", p, q);
    }
    return 0;
}