UVa 10619 - Advanced Causal Measurements (ACM)

// UVa 10619 - Advanced Causal Measurements (ACM)

#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

struct dot {
	int x, i, z;
};

vector<dot> line;
int n, m, x[100000], t[100000];
bool sat[100000];

bool operator <(dot a, dot b) {
	return a.x < b.x || (a.x == b.x && a.z < b.z);
}

int count(int tt) {
	line.clear();
	for (int i = 0; i < n; i++) {
		int x1 = x[i] - (t[i] - tt);
		int x2 = x[i] + (t[i] - tt);
		line.push_back( { x1, i, 1 });
		line.push_back( { x2, i, 2 });
	}
	sort(line.begin(), line.end());
	memset(sat, false, sizeof(sat));
	int c = 0;
	for (int i = 0; i < line.size();) {
		c++;
		int j = i;
		while (i < line.size() && (line[i].z == 1 || sat[line[i].i]))
			i++;
		while (i < line.size() && line[i].x == line[i - 1].x)
			i++;
		for (; j < i; j++)
			sat[line[j].i] = true;
		while (i < line.size() && sat[line[i].i])
			i++;
	}
	return c;
}

int main() {
	int cases;
	scanf("%d", &cases);
	for (int cas = 1; cas <= cases; cas++) {
		scanf("%d%d", &n, &m);
		int t1 = 0, t2 = 0, x1 = 0, x2 = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &t[i], &x[i]);
			if (x[i] > x[x2])
				x2 = i;
			if (x[i] < x[x1])
				x1 = i;
			if (t[i] < t[t1])
				t1 = i;
			if (t[i] > t[t2])
				t2 = i;
		}

		int ini = t[t1] - max(x[x2] - x[x1], t[t2] - t[t1]);
		int fin = t[t1];
		int sol = ini;
		while (ini <= fin) {
			int mid = (ini + fin) / 2;
			int mm = count(mid);
			if (mm <= m) {
				ini = mid + 1;
				sol = mid;
			} else
				fin = mid - 1;
		}
		printf("Case %d: %d\n", cas, sol);
	}
	return 0;
}