1961.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1961 on 2006-02-21 at 14:39:12 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef pair<int, double> pid;
const int MAX = 512;
const double INF = 1e10;

struct cmp {
	bool operator ()(const pid& p1, const pid& p2) const {
		return p1.second > p2.second;
	}
};

class Point {
public:
	int x, y;
	void make();
	double dis(const Point&) const;
};
void Point::make() {
	scanf("%d %d", &x, &y);
}
double Point::dis(const Point& p) const {
	return sqrt(1.0*(x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
}

Point outpost[MAX];
double edge[MAX];
int s, n;

void Prim();

int main()
{
	int t, T, i;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &s, &n);
		for(i = 0; i < n; i++) outpost[i].make();
		double d = 0;
		if(s < n) { Prim(); d = edge[n-s]; }
		printf("%.2lf\n", d);
	}
	
	return 0;
}

void Prim()
{
	int en, i;
	double d[MAX] = { 0 };
	bool vst[MAX] = { false };
	for(i = 1; i < n; i++) d[i] = INF;
	for(en = 0; en < n; en++) {
		double mind = INF; int mini;
		for(i = 0; i < n; i++)
			if(!vst[i] && mind > d[i]) mind = d[i], mini = i;
		vst[mini] = true; edge[en] = mind;
		for(i = 0; i < n; i++)
			if(!vst[i]) d[i] = min(d[i], outpost[mini].dis(outpost[i]));
	}
	
	sort(edge, edge+n);
}