题目大意：有一些长度不均匀的线段分布在一个一维的轴上，这些线段间存在相交但不存在包含，要求把一些线段修剪，使之最终满足每个线段最后变成其子线段，且每个线段长度相等。求出这些线段最大可能的长度，用最简分数表示。线段数≤10^5，线段范围≤10^9
思路1：二分+贪心。因为线段是相交但不包含的，所以左端点的排序和右端点的排序是一致的，就有一个很轻易的贪心想法，就是按照同一个方向放（全部从左到右或者全部从右到左），放到不能放为止，答案一定最优，所以二分一下就可以出答案了。
思路2:：凸壳上二分？不过没去写= =
关于输出最简分数：答案的分母一定小于等于n，可以这么理解不管怎么交叉，最后都是把都可以拼凑好，看成把整段的平均分成n分，最后再约分下就差不多了。
Ps：注意精度。
贴代码
const dt=1e-10; var n,Q,t:longint; ansa,ansb,ans1,ans2:int64; ans:double; c:array[0..100005]of double; a,b:array[0..100005]of longint; procedure swap(var x,y:longint); var t:longint; begin t:=x;x:=y;y:=t; end; procedure qsort(L,R:longint); var i,j,mid:longint; begin i:=L;j:=R;mid:=a[random(R-L+1)+L]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin swap(a[i],a[j]);swap(b[i],b[j]); inc(i);dec(j); end; until i>j; if i<R then qsort(i,R); if L<j then qsort(L,j); end; function max(x,y:double):double; begin if x>y then exit(x) else exit(y); end; function check(x:double):boolean; var i,j:longint; begin c[1]:=a[1]; for i:=2 to n do c[i]:=max(c[i-1]+x,a[i]); for i:=1 to n do if c[i]+x>b[i] then exit(false); exit(true); end; function gcd(x,y:int64):int64; begin if y=0 then exit(x) else exit(gcd(y,x mod y)); end; procedure main; var L,R,mid:double; i:longint; k:int64; begin readln(n); for i:=1 to n do readln(a[i],b[i]); qsort(1,n); L:=0;R:=1000000000;ans:=0; for i:=1 to n do if b[i]-a[i]<R then R:=b[i]-a[i]; while R-L>=dt do begin mid:=(L+R)/2; if check(mid) then begin ans:=mid; L:=mid+dt; end else R:=mid-dt; end; ansb:=1; ansa:=round(1*ans); for i:=2 to n do begin ans1:=i; ans2:=round(ans1*ans); if abs(ans2/ans1-ans)<abs(ansa/ansb-ans) then begin ansa:=ans2;ansb:=ans1; end; end; k:=gcd(ansa,ansb); writeln(ansa div k,'/',ansb div k); end; begin assign(input,'field.in');reset(input); assign(output,'field.out');rewrite(output); readln(Q); for t:=1 to Q do main; close(input);close(output); end. 【写的有漏洞的，欢迎路过大神吐槽】2017/3/9 15:15:26
Ending.
