题目说的有点诡异，一开始没想到二分，想直接通过半平面交来解或者是线性规划。。。
描述下题目平面上有一些点（x,t）（题目中描述的是(t,x)，然后t是纵坐标，有点不舒服），然后满足t2 >= t1+|x2-x1|的点（t1,x1）称为点(x2,t2)的前导点。现在知道平面点集以及其前导点的个数，问其前导点集中t的最大值。
根据不等式，可以发现每个点的前导点集范围是一个以该点为顶点的三角形区域（根据不等式约束画个图看看就明白了），然后可以通过二分求得t，关于判断当前t的可行性，将每个点表示为合法区间[x2-(t2-t1),x2+t2-t1]，然后求这些区间的最小覆盖数（就是求得一些子区间，使得这些子区间包含于原区间）。这个问题可以通过贪心算法，以区间右端点为第一关键字，左端点为第二关键字进行排序，然后每次贪心的选择当前区间的右端点作为子区间，统计要导出全部区间需要子区间的个数num。
代码如下：
1 import java.io.*;
2 import java.util.Arrays;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
9 //static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"))));
10 static final int readInt() throws Exception
11 {
12 in.nextToken();
13 return (int)in.nval;
14 }
15 static class node implements Comparable<node>
16 {
17 int t,x,s,e;
18 public int compareTo(node pos)
19 {
20 if(e!=pos.e) return e-pos.e;
21 else return s-pos.s;
22 }
23 }
24 static node data[]=new node[100005];
25 public static void main(String[] args) throws Exception{
26 int n=readInt();
27 for(int i=0;i<100005;i++)
28 data[i]=new node();
29 for(int test=1;test<=n;test++)
30 {
31 int num=readInt(),limit=readInt(),e=4000000,s=-4000000;
32 for(int i=0;i<num;i++)
33 {
34 data[i].t=readInt();
35 data[i].x=readInt();
36 e=Math.min(e, data[i].t);
37 }
38 while(s<=e)
39 {
40 int mid=(s+e)>>1,count=1;
41 for(int i=0;i<num;i++)
42 {
43 data[i].s=data[i].x-data[i].t+mid;
44 data[i].e=data[i].x+data[i].t-mid;
45 }
46
47 Arrays.sort(data,0,num);
48 int laste=data[0].e;
49 for(int i=1;i<num;i++)
50 if(data[i].s<=laste)
51 continue;
52 else
53 {
54 count++;
55 laste=data[i].e;
56 }
57 if(count<=limit)
58 s=mid+1;
59 else
60 e=mid-1;
61 }
62 System.out.println("Case "+test+": "+e);
63 }
64
65 }
66
67 }
68