読者です 読者をやめる 読者になる 読者になる

JOI 2008 春合宿 day2-2 「Cheeting」

JOI

二分探索にしか見えない。。
思った以上に簡単だった。

汚いソースですが。

#include<cstdio>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;



int main(){
	int n, m, a, b, ld = 0, rd = 1000000000, d, nx, ny, xi, yi;
	vector<int> x, y;
	
	scanf("%d%d",&n,&m);
	
	rep(i,m){
		scanf("%d%d",&a,&b);
		x.pb(a); y.pb(b);
	}
	
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	
	while(ld < rd){
		d = (ld+rd)/2;
		nx = 0; ny = 0; xi = 1; yi = 1;
		for(int j = 1; j < m; j++){
			nx += x[j] - x[j-1];
			ny += y[j] - y[j-1];
			
			if(nx > d){xi++; nx = 0;}
			if(ny > d){yi++; ny = 0;}
		}
		
		if(xi + yi > n) ld = d+1; else rd = d;
	}
	
	printf("%d\n", ld);
	
	return 0;
}