JOI春合宿 2008-day2 cheating

問題文 : カンニング対策 (pdf注意, 3枚目)

解法 : 監視する装置の範囲の最大値を求めれば良いから, すべての装置の精度を等しいものとして考える.
すると, 端から貪欲的に装置を置いていける.
装置の範囲の最大値は, 二分探索で決めてやることで, O(Mlog(max(x, y)))時間でこの問題を解くことができる.

コード :

#include <cstdio>
#include <algorithm>

using namespace std;

int n, m;

typedef struct {
	int x, y;
} Point;

Point sx[200000], sy[200000];

bool compx(const Point &a, const Point &b)
{
	return (a.x < b.x);
}

bool compy(const Point &a, const Point &b)
{
	return (a.y < b.y);
}

bool canControl(int dmax)
{
	int piv = -1000000001;
	int lim = n;
	
	for (int i = 0; i < m; i++){
		if (piv + dmax < sx[i].x){
			piv = sx[i].x;
			lim--;
		}
		if (lim == -1){
			return (false);
		}
	}
	
	piv = -1000000001;
	
	for (int i = 0; i < m; i++){
		if (piv + dmax < sy[i].y){
			piv = sy[i].y;
			lim--;
		}
		if (lim == -1){
			return (false);
		}
	}
	
	return (true);
}


int main(void)
{
	int left, right, center;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++){
		int tx, ty;
		scanf("%d %d", &tx, &ty);
		sx[i].x = sy[i].x = tx;
		sx[i].y = sy[i].y = ty;
	}
	sort(sx, sx + m, compx);
	sort(sy, sy + m, compy);
	
	left = 0, right = 1000000000;
	
	while (left != right){
		center = (left + right) / 2;
		
		if (canControl(center) == true){
			right = center;
		}
		else {
			left = center + 1;
		}
	}
	
	printf("%d\n", m ? left : right);
	
	return (0);
}