題目說的有點詭異，一開始沒想到二分，想直接通過半平面交來解或者是線性規(guī)劃。。。
描述下題目平面上有一些點（x,t）（題目中描述的是(t,x)，然后t是縱坐標，有點不舒服），然后滿足t2 >= t1+|x2-x1|的點（t1,x1）稱為點(x2,t2)的前導點。現(xiàn)在知道平面點集以及其前導點的個數(shù)，問其前導點集中t的最大值。
根據(jù)不等式，可以發(fā)現(xiàn)每個點的前導點集范圍是一個以該點為頂點的三角形區(qū)域（根據(jù)不等式約束畫個圖看看就明白了），然后可以通過二分求得t，關于判斷當前t的可行性，將每個點表示為合法區(qū)間[x2-(t2-t1),x2+t2-t1]，然后求這些區(qū)間的最小覆蓋數(shù)（就是求得一些子區(qū)間，使得這些子區(qū)間包含于原區(qū)間）。這個問題可以通過貪心算法，以區(qū)間右端點為第一關鍵字，左端點為第二關鍵字進行排序，然后每次貪心的選擇當前區(qū)間的右端點作為子區(qū)間，統(tǒng)計要導出全部區(qū)間需要子區(qū)間的個數(shù)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