题意

给定一些点的坐标代表“事件”，每个“事件”可以有一些“因事件”，只要“因事件”的坐标落在给定不等式确定的范围之内即可。另给定数$m$表示至多有$m$个“因事件”。求对于给定的所有事件，它们的“因事件”中，最早发生的那一个事件的最迟发生时间（即最大的纵坐标）。

解题思路

对于一个给定的$k$值，最优的情况是所有的$m$个$cause$都是在$k$时间到达的（越早越好），因此这可以成为我们的一个假设。然后我们将存储在$a$数组中的点对按照$x$从小到大的顺序排列，那么是不是就形成了这样一个图？$y=k$是我们所有的$cause$所在的直线，每个因事件就是y=k轴上的一个点，此时求出最少需要多少因事件才能覆盖图上的所有点（转化完毕）。唯一不同的是，这里的每个点比如$P1(x,y)$，能覆盖它的范围不是一个圆，而是一个等腰直角三角形，横坐标处于$x1-x2$范围内的因事件就可以产生P1事件。$x1=x-(y-k)$, $x2=x+y-k$，这两个坐标也很好计算，然后就二分答案即可。

标程

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define ll long long
#define inf 0x3f3f3f3f
#define P pair<int,int>
#define MAX 100005

struct E {
    int t, x;
    E(int a = 0, int b = 0) : t(a), x(b) {}
};

bool cmp(const E& e1, const E& e2) {
    if (e1.x == e2.x) return e1.t < e2.t;
    else return e1.x < e2.x;
}

E a[MAX];
int T, n, m, l, r;

bool check(int k) {
    int x = (a[0].t - k) + a[0].x;
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (x < a[i].x - (a[i].t - k)) {
            x = a[i].t - k + a[i].x;
            cnt++;
            if (cnt > m) return false;
        }
        else if (a[i].t - k + a[i].x < x) {
            x = a[i].t - k + a[i].x;
        }
    }
    return true;
}

int main() {
    scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        scanf("%d %d", &n, &m);
        r = inf;
        l = -2000010;
        for (int j = 0; j < n; j++) {
            scanf("%d %d", &a[j].t, &a[j].x);
            if (a[j].t < r) r = a[j].t;
        }
        r++;
        sort(a, a + n, cmp);
        while (r - l > 1) {
            int mid = (r + l) >> 1;
            if (check(mid)) l = mid;
            else r = mid;
        }
        printf("Case %d: %d\n", i, l);
    }
    return 0;
}