[ create a new paste ] login | about

Link: http://codepad.org/iEpS82wC    [ raw code | fork ]

C++, pasted on Apr 1:
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
using namespace std;

const int MAX_N = 10003;
double pos[MAX_N];
int n,m;

bool check(double d) {
//	cout<<"d="<<d<<endl;
	int id=0;
	int sx=-1;
	for (int x=0;m>x;x++) {
//		cout<<"x="<<x<<" , id="<<id<<endl;
		while (pos[id]<=sx) id++;
		sx = pos[id++] + 2.0*d;
		if (id>=n) return true;
	}
	if (sx>=pos[n-1]) return true;
	return false;
}

int main () {
	int T;
	cin >> T;
	while (T--) {
		cin >> m >> n;
		for (int x=0;n>x;x++) {
			int i;
			cin >> i;
			pos[x]=i;
		}
		sort(pos,pos+n);
		pos[n]=1234567.0;
		double l=0.0,r=100000.0;
		while (r-l>1e-9) {
			double mid=(l+r)/2;
			if (check(mid)==true) r=mid;
			else l=mid;
		}
		cout << fixed << setprecision(1) << r << endl;
	}
}

/*
1
2 3
1 5 7

1
5 9
3 4 6 7 9 10 11 12 16
*/


Create a new paste based on this one


Comments: