描述 Description
一维的世界就是一个数轴。这个世界的狭小我们几乎无法想象。
在这个数轴上，有N个点。从左到右依次标记为点1到N。第i个点的坐标为Xi。经过漫长时间的物理变化和化学变化，这个一维世界中产生了一个高等智慧文明，而这N个点都成为了这个文明的一座城市。而点1则成为了这个文明的首都。
出于政治上和经济上的需要，首都不能和任何城市相距太远。所以政府决定在某两个城市耗巨资修建虫洞。一个修建了虫洞的城市可以瞬移到另一个修建了虫洞的城市，从而大大缩短了N个城市相互之间的距离。原先从任意城市i到城市j的路程等于它们的距离|Xi - Xj|，而现在若两个城市附近都有修建了虫洞的城市，则可以先从i移动到附近的虫洞瞬移到城市j附近的虫洞再移动到j。
政府希望在两个合适的城市修建虫洞，使得修建虫洞以后从点1移动到任意城市经过的最短路程的最大值尽量小。请你计算这个路程的最小值是多少。
输入包含多组数据。
输入格式 Input Format
第一行包括一个正整数T,表示有T组测试数据。接下来依次是T组测试数据。
每组测试数据的第一行包括一个整数N，表示有N个城市。第二行，N个递增的整数，依次表示N个城市的坐标。
输出格式 Output Format
输出文件包括T行，每行一个整数，依次表示每组测试数据的答案。
样例输入
2
3
0 1 21
5
0 100 101 102 103
样例输出
1
2
思路是对的。。。可是代码写搓了。。。无力回天。。。
下面来说说思路。
首先我们可以证明，第一个虫洞一定放在1号城市。
一个虫洞建立在A点，另一个建在C点，很显然，当B,C点将整段长为S的AD大致等分成三份时，到A点的距离都最短，大约为 S/3 （视数据不同，结果也有一定的差距）
如果我们没有把第一个虫洞建立在A点，而是建立在了B点，第二个虫洞在D点，而AB的距离为X，AE的距离仍为S，我们可以看到，当C点与D点将BE近似等分成三分时，仍然可以得到最优解，但是此时的最优解为：X+(S-X)/3=(S+2X)/3，很显然大于把虫洞建立在A点上的情况。
虽然可能会因为城市分布的或密或疏而无法真正的将图三等分，但是，尽量接近三等分可以使本题最优。
做法，现在就清晰了。
从左向右扫描第二个虫洞的位置，然后，我们通过二分查找两虫洞之间的城市，进行比较，找出最优解即可。代码时间复杂度O(N*T*log2(N))，可以应付该题了。
program vijos1763;
var
qq,ss,s,mid,left,right,need,temp,ans,q,t,i,n:longint;
p:array[1..200000] of longint;
function min(i,j:longint):longint;
begin
if i<j then
exit(I);
exit(j);
end;
function max(i,j:longint):longint;
begin
if i>j then
exit(i);
exit(j);
end;
function dich(l,r:longint):longint;
var
temp,i,j,mid,s1,s2:longint;
begin
if l+1=r then
exit(0);
temp:=0;
i:=l;
j:=r;
while l<=r do
begin
mid:=(l+r) shr 1;
s1:=p[mid]-p[i];
s2:=p[j]-p[mid];
temp:=max(temp,min(s1,s2));
if s1>s2 then
r:=mid-1
else
l:=mid+1;
end;
exit(temp);
end;
begin
readln(t);
for q:=1 to t do
begin
readln(n);
for i:=1 to n do
read(p[i]);
readln;
ans:=maxlongint;
for i:=2 to n do
begin
temp:=p[n]-p[i];
temp:=max(temp,dich(1,i));
ans:=min(ans,temp);
end;
writeln(ans);
end;
end.