OJ Board

Code: Select all

typedef long double ld;
struct Point
{
	ld x, y;
	void print()
	{
		cout << x << " " << y << endl;
	}
};
const int MAX = 210;
Point p[MAX];
const ld EPS = 1e-9;
bool myLess(ld a, ld b)
{
	if(fabs(a-b) <= EPS) return false;
	return (a + EPS) < b;
}

bool myGreater(ld a, ld b)
{
	if(fabs(a-b) <= EPS) return false;
	return a > (b + EPS);
}

bool myLessEq(ld a, ld b)
{
	if(fabs(a-b) <= EPS) return true;
	return (a + EPS) < b;
}

bool isInside(Point p, Point center, ld R)
{
	return myLessEq( sqr(p.x - center.x) + sqr(p.y - center.y), sqr(R) );
}

inline bool operator==(const Point& p1, const Point& p2)
{
    return fabs(p1.x - p2.x) < EPS && fabs(p1.y - p2.y) < EPS;
}

ld dist(Point p1, Point p2)
{
	return sqrt( sqr(p1.x - p2.x) + sqr(p1.y - p2.y) );
}
// find the center of the circle from 2 points on the circle and the radius
// can be 2 centers
vector<Point> getCenter(Point p1, Point p2, ld R)
{
	vector<Point> res;
	ld x3 = (p1.x + p2.x) / 2., y3 = (p1.y + p2.y) / 2.;
	ld q = dist(p1, p2);
	ld x = x3 + sqrt(sqr(R) - sqr(q/2)) * (p1.y - p2.y) / q;
	ld y = y3 + sqrt(sqr(R) - sqr(q/2)) * (p2.x - p1.x) / q;
	res.push_back((Point){x, y});
	x = x3 - sqrt(sqr(R) - sqr(q/2)) * (p1.y - p2.y) / q;
	y = y3 - sqrt(sqr(R) - sqr(q/2)) * (p2.x - p1.x) / q;
	res.push_back((Point){x, y});
	if(res[0] == res[1])
	  return vector<Point>(res.begin() + 1, res.end());
	return res;
}

int main ()
{
	int T;
	scanf("%d\n\n", &T);
	string s;
	For(tests, T)
	{
		double x, y;
		int idx = 0;
		while(getline(cin, s) && s != "")
		{
			istringstream in(s);
			in >> x >> y;
			p[idx++] = (Point){(ld)x, (ld)y};
		}

		ld R = 2.5;
		int res = 1;
		For(i, idx)
		{
			Fori(j, i + 1, idx)
			{
				ld q = dist(p[i], p[j]);
				if(myGreater(q, 5.)) continue;
				vector<Point> v = getCenter(p[i], p[j], R);
				For(k, sz(v))
				{
					Point center = v[k];
					int cur = 0;
					For(ii, idx)
					{
						if(isInside(p[ii], center, R))
						  ++cur;
					}
					res = max(res, cur);
				}
			}
		}
		
		// consider every point as a center
		For(i, idx)
		{
      	                        Point center = p[i];
				int cur = 0;
				For(ii, idx)
				{
					if(isInside(p[ii], center, R))
					  ++cur;
				}
				res = max(res, cur);
		}
		cout << res << endl;
	}
	return 0;
}