思路和yzhw牛一样

1. 每一个event它对应的可能的cause是这个event点下面的三角形区域(这个区域是无穷大的)
2. 问 “the latest time at which the earliest cause could have occurred” 就相当于用一条平行于x轴的直线 t=t0 把这些三角形区域拦腰切断(当然, 此线必须在所有event下面), 只准在腰以上的三角形里放cause. 然后用二分求到一个恰好不能再往上移了的直线, 就成了.
3. 可行性判断, 用贪心. 三角形们和直线相交的那个区间就可以代表这个三角形, 因为放在直线以上的cause都可以垂直投影到直线上, 效果更佳.
4. 在这些所有的区间中, 要找出最少的cause个数n, 使得每个区间内都能包含至少一个的cause. 如果这个n<=m, 那么这条直线ok, 否则不ok.
5. 怎么判断呢, 引用yzhw “以区间右端点为第一关键字，左端点为第二关键字进行排序，然后每次贪心的选择当前区间的右端点作为子区间，统计要导出全部区间需要子区间的个数num。” (其实第二关键字是不用排序的, 无所谓).
6. 对应5, 举个例子

---------(A)
   ------
  -------
     --------
        -------
    ------------
                 -----(B)
.....           ......

按照右边界升序排序, 123行显然要放一个点在他们区间里, 放哪呢, “不妨”(这个词表达能力太强了)放在最右边, 即点A处. 然后我们下面所有的左边界<=A的都可以ban掉了, 因为右边界是升序排序的. 这个操作后得到的问题是最优子结构的. 然后到了第7行, A不给力了, "不妨"取一个B. 这些操作整合一下就是维护一个变量rightEdge, 一旦rightEdge不给力就取一个当前区间最右边的点, 同时更新rightEdge至这个点. 之前的错误: 对应6的例子, 我以前是按左边界优先于右边界升序排序的, 那样虽然也对但是无法处理一个区间包含另一个区间的情况, 需要filter一下, filter的过程能写成O(n), 我比较愚钝写的n^2一个case要算2分钟 - -.. 总之这个贪心记住了, 求最小覆盖数 代码点下面:

#include <stdio.h>
#include <stdlib.h>
#define DEBUG 0

struct Event {
    int t,x,l,r;
    void calc() {
        l=x-t;
        r=x+t;
    }
};

int comp(const void *__a,const void *__b) {
    Event *a=(Event *)__a;
    Event *b=(Event *)__b;
    return a->r-b->r;
}

int greed(Event A[],int n,int t0) {
    int *l=(int *)malloc(sizeof(int)*(n+1));
    int *r=(int *)malloc(sizeof(int)*(n+1));
    for(int i=1;i<=n;i++) {
        l[i]=A[i].l+t0;
        r[i]=A[i].r-t0;
    }

    int count=0;
    int rightEdge=-2e9;
    for(int i=1;i<=n;i++) {
        if(l[i]<=rightEdge)
            continue;
        count++;
        rightEdge=r[i];
    }
    free(l);
    free(r);
    return count;
}

int main() {
    int N;
    FILE *fp=fopen("B.1.dat","r");
    if(DEBUG) {
        fscanf(fp,"%d",&N);
    }
    else
        scanf("%d",&N);
    for(int T=1;T<=N;T++) {
        int n,m;
        if(DEBUG)
            fscanf(fp,"%d%d",&n,&m);
        else
            scanf("%d%d",&n,&m);
        Event *A=(Event *)malloc(sizeof(Event)*(n+1));
        for(int i=1;i<=n;i++) {
            int t,x;
            if(DEBUG)
                fscanf(fp,"%d%d",&t,&x);
            else
                scanf("%d%d",&t,&x);
            A[i].t=t;
            A[i].x=x;
            A[i].calc();
        }

        qsort(A+1,n,sizeof(Event),comp);

        int up=1e6;
        int down=-2e6;   //because, (-1e6,-1e6) and (-1e6,1e6) intersect at (-2e6,0)
        for(int i=1;i<=n;i++)
            up=A[i].t<up?A[i].t:up;
        while(1) {
            if(up==down)
                break;
            if(up==down+1) {
                if(greed(A,n,up)<=m) {
                    down=up;
                    break;
                }
                else {
                    up=down;
                    break;
                }
            }
            int mid=(up+down)/2;
            if(greed(A,n,mid)>m) {
                up=mid-1;
                continue;
            }
            else {
                down=mid;
                continue;
            }
        }
        free(A);
        printf("Case %d: %d\n",T,up);
    }
    return 0;
}