UVa 11574 - Colliding Traffic

// UVa 11574 - Colliding Traffic

#include <cmath>
#include <math.h>
#include <algorithm>
#include <limits>
#include <stdio.h>
using namespace std;

const int maxn = 1000;
const double epsilon = 0;

int main() {
	int cases;
	for (scanf("%d", &cases); cases; cases--) {
		int n;
		double r;
		scanf("%d%lf", &n, &r);
		double inx[maxn], iny[maxn], ind[maxn], ins[maxn], ina[maxn], inb[maxn];
		for (int i = 0; i < n; i++) {
			scanf("%lf%lf%lf%lf", &inx[i], &iny[i], &ind[i], &ins[i]);
			ind[i] = 90 - ind[i];
			while (ind[i] < 0)
				ind[i] += 360;
			ind[i] = (ind[i] / 180) * M_PI;
			ina[i] = cos(ind[i]) * ins[i];
			inb[i] = sin(ind[i]) * ins[i];
		}

		double sol = numeric_limits<double>::max();

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {

				double da = ina[i] - ina[j];
				double db = inb[i] - inb[j];
				double dx = inx[i] - inx[j];
				double dy = iny[i] - iny[j];

				double a = da * da + db * db;
				double b = 2 * da * dx + 2 * db * dy;
				double c = dx * dx + dy * dy - r * r;
				double D = b * b - 4 * a * c;

				if (D < -epsilon)
					continue;
				double t1 = (-b + sqrt(D)) / (2 * a);
				double t2 = (-b - sqrt(D)) / (2 * a);
				if (t1 > t2)
					swap(t1, t2);

				double ini1, ini2, fin1, fin2;
				if (a > epsilon) {
					ini1 = max(t1, 0.0);
					fin1 = t2;
					ini2 = 0;
					fin2 = -1;
				} else if (a < -epsilon) {
					ini1 = 0;
					fin1 = t1;
					ini2 = max(t2, 0.0);
					fin2 = ini2 + 1;
				} else {
					if (b > epsilon) {
						ini1 = 0;
						fin1 = t1;
						ini2 = 0;
						fin2 = -1;
					} else if (b < -epsilon) {
						ini1 = max(t2, 0.0);
						fin1 = ini1 + 1;
						ini2 = 0;
						fin2 = -1;
					} else if (c <= epsilon) {
						ini1 = 0;
						fin1 = 1;
						ini2 = 0;
						fin2 = -1;
					} else {
						ini1 = 0;
						fin1 = -1;
						ini2 = 0;
						fin2 = -1;
					}
				}

				//cout << "D: " << ini1<< ' ' << fin1 << endl;
				//cout << "D: " << ini2<< ' ' << fin2 << endl;
				if (ini1 <= fin1 && ini1 < sol)
					sol = ini1;
				if (ini2 <= fin2 && ini2 < sol)
					sol = ini2;

			}

		}

		if (sol == numeric_limits<double>::max())
			printf("No collision.\n");
		else
			printf("%.f\n", sol);

	}
	return 0;
}