UVa 10136 - Chocolate Chip Cookies

// UVa 10136 - Chocolate Chip Cookies

#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;

struct point {
	double x, y;
};

point p[200];

//const double size = 5;
const double lim = 2.5 * 2.5;
const double epsilon = 1e-6;

double dist2(point a, point b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

point point_in_dir(point p, point q, double r) {
	double dx = q.x - p.x;
	double dy = q.y - p.y;
	double rat = r / sqrt(dist2(p, q));
	point m = { p.x + rat * dx, p.y + rat * dy };
	return m;
}

bool circle2PtsRad(point p1, point p2, double r, point *c) {
	double d2 = dist2(p1, p2);
	double det = r * r / d2 - 0.25;
	if (det < 0.0)
		return false;
	double h = sqrt(det);
	c->x = (p1.x + p2.x) * 0.5 + (p1.y - p2.y) * h;
	c->y = (p1.y + p2.y) * 0.5 + (p2.x - p1.x) * h;
	return true;
}

int main() {
	int t;
	cin >> t;
	string line;
	getline(cin, line);
	getline(cin, line);
	for (; t; t--) {
		int n = 0;
		while (getline(cin, line) && line.length() > 0) {
			istringstream strm(line);
			strm >> p[n].x >> p[n].y;
			n++;
		}
		int sol = n ? 1 : 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				if (i != j) {
					point c1, c2;
					if (circle2PtsRad(p[i], p[j], 2.5, &c1)) {
						circle2PtsRad(p[j], p[i], 2.5, &c2);
						int one = 0, two = 0;
						for (int k = 0; k < n; k++) {
							if (dist2(c1, p[k]) <= lim + epsilon)
								one++;
							if (dist2(c2, p[k]) <= lim + epsilon)
								two++;
						}
						if (one > sol)
							sol = one;
						if (two > sol)
							sol = two;
					}

					int ths = 0;
					point center = point_in_dir(p[i], p[j], 2.5);
					for (int k = 0; k < n; k++)
						if (dist2(center, p[k]) <= lim + epsilon)
							ths++;
					if (ths > sol)
						sol = ths;
				}
		}
		cout << sol << endl;
		if (t > 1)
			cout << endl;
	}
	return 0;
}