#include <iostream>
#include <cassert>
#include <ctime>
#include <string>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
const int N = 7;
const double eps = 1e-7;
double PI;
 
int n, s, x[N], y[N], v[N], t;
double r[N];
 
int circlesIntersectionPoints(double x1,double y1,double r1,double x2,double y2,double r2,
		double &xp1,double &yp1,double &xp2,double &yp2)
{
	double a=atan2(y2 - y1, x2 - x1);
	double s=hypot(x1 - x2, y1 - y2);
	if(s > r1 + r2 + eps)return 0;
	double b=acos((r1 * r1 + s * s - r2 * r2) / (2 * r1 * s));
	if(abs((r1 * r1 + s * s - r2 * r2) / (2 * r1 * s))>1)
		b=(r1 * r1 + s * s - r2 * r2)>=0?0:PI;
	xp1=cos(a+b)*r1+x1;
	xp2=cos(a-b)*r1+x1;
	yp1=sin(a+b)*r1+y1;
	yp2=sin(a-b)*r1+y1;
	if(abs(s-r1-r2)<eps||abs(s-abs(r1-r2))<eps)
		return 1;
	if(s<abs(r1-r2)-eps)return 0;
	return 2;
}
 
bool disjoint(int a, int b) {
	return hypot(x[a] - x[b], y[a] - y[b]) > r[a] + r[b] + eps;
}
 
bool inside(double xx, double yy, int a) {
	return hypot(x[a] - xx, y[a] - yy) < r[a] + eps;
}
 
bool intersects() {
	for( int i = 0; i < n; i ++ )
		for( int j = i + 1; j < n; j ++ )
			if( disjoint(i, j) )
				return false;
	for( int i = 0; i < n; i ++ )
		for( int j = i+1; j < n; j ++ ) {
			double xp[2], yp[2];
			int c = circlesIntersectionPoints(x[i], y[i], r[i], x[j], y[j], r[j], xp[0], yp[0], xp[1], yp[1]);
			if( c != 0 ) {
				for( int p = 0; p < c; p ++ ) {
					bool valid = true;
					for( int k = 0; k < n && valid; k ++ )
						if( !inside(xp[p], yp[p], k) )
							valid = false;
					if( valid )
						return true;
				}
			}
		}
	for( int i = 0; i < n; i ++ ) {
		bool valid = true;
		for( int j = 0; j < n && valid; j ++ )
			if( !inside(x[i], y[i], j) )
				valid = false;
		if( valid )
			return true;
	}
	return false;
}
 
bool check( double x ) {
	int order[N];
	for( int i = 0; i < n; i ++ )
		order[i] = i;
	do {
		for( int i = 0; i < n; i ++ )
			if( i * s > x )
				r[order[i]] = 0;
			else
				r[order[i]] = (x - i * s) * v[order[i]];
		if( intersects() ) {
			return true;
		}
	} while( next_permutation(order, order + n) );
	return false;
}
 
double solve() {
	double L = 0, R = 1e12;
	while( fabs(L - R) > 1e-4 ) {
		double M = (L + R) * 0.5;
		if( check(M) )
			R = M;
		else
			L = M;
	}
	return L;
}
 
void readInput() {
	cin >> n >> s;
	assert( n > 0 && n < 8);
	assert( s >= 0 && s <= 100 );
	for( int i = 0; i < n; i ++ ) {
		cin >> x[i] >> y[i] >> v[i];
		assert( x[i] >= -2000 && x[i] <= 2000 );
		assert( y[i] >= -2000 && y[i] <= 2000 );
		assert( v[i] >= 1 && v[i] <= 200 );
	}
}
 
int main() {
	int cl = clock();
	freopen("atoms.in", "r", stdin);
	freopen("atoms.out", "w", stdout);
	PI = acos(-1.0);
	cout.precision(2);
	cout.setf( ios::fixed | ios::showpoint );
	for( cin >> t; t--; ) {
		readInput();
		cerr << n << " " << s << endl;
		cout << solve() << endl;
	}
	cerr << (clock() - cl) * 1. / CLOCKS_PER_SEC << endl;
	return 0;
}

 
implementation/iaumc3_atoms.txt · Last modified: 2009/07/19 13:02 by hadi
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki