管理人の独り言（プログラミング関連）

1533： ◆adhRKFl5jU：2009/03/01(日) 18:44:49: jid37
問題番号 10
点数 100
-----
/*
TASK: Cheating
LANG: C++
NAME: Kazuhiro Hosaka JPN13
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <bitset>
#include <complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i=a; i!=b; ++i) cout << *i << " "; cout << endl; }
template<class T> void pvp(T a, T b) { for (T i=a; i!=b; ++i) cout << "(" << i->first << ", " << i->second << ") "; cout << endl; }

int N,M;
int X[100010],Y[100010];

int need(int a[], int d) {
int i,ret=0;
int tmp=-d-1;
for (i=0; i<M; ++i) {
if (tmp < a[i]) {
tmp = a[i] + d;
++ret;
}
}
return ret;
}

int main() {
//freopen("cheating.in", "r", stdin);

int i;

scanf("%i%i", &N, &M);

for (i=0; i<M; ++i) {
scanf("%i%i", &X[i], &Y[i]);
}
sort(X, X+M);
sort(Y, Y+M);

int s=-1,e=1000000000;
for (int h; h=(s+e)/2, e-s>1; ) {
(need(X, h) + need(Y, h) > N) ? s = h : e = h;
}

printf("%i\n", e);

return 0;
}

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）

掲示板管理者へ連絡無料レンタル掲示板