10136 - Chocolate Chip Cookies

[Miguel Angel]

Someone can give me a hint, i have no idea on how to solve it?

[Abednego]

Take any optimal solution. It corresponds to some circle in the plane. We can always move that circle until it touches at least 2 cookies. Once we have 2 cookies, and we know the radius of the circle, the circle is unique. Use these facts to find a fast solution.

My question is this: how is it possible to get a Presentation Error on this problem!? I tried printing empty lines between cases, after each case and not printing them at all.

[Darko]

My solution is O(n^3), I am not sure how to speed that up (Referring to the "Use these facts to find a fast solution." part)

I haven't done anything special to print the results - I am not sure why you are getting PE.

Maybe you are dealing with special cases separately and forgetting to print a blank line in there (or printing it even if you shouldn't)?

[Quantris]

Careful Igor -- unless the two points are a full diameter apart, they actually determine two circles with a given radius (or none, if they are further apart than a diameter), not a unique one.

[bourne]

@Darko

Can you explain your O(n^3) idea. A brute force approach I can think of is to draw all possible circles using triplets of points and count the maximum no of points residing on the circle. But that would be O(n^4). How to do it in O(n^3)?

[Abednego]

@bourne

You know the circle's radius.

[armansuleimenov]

My algorithm is the following:
1) Consider all pairs of points, for each pair of points (A, B): if they are at <=5 cm distance from each other, then find the centers of two possible circles with points
A and B on the circumference, count how many of the points given are inside these circles
2) Draw a circle with center at each point given, count how many points are inside this circle

However, I keep getting WA. Any idea what's wrong with my approach?

My code is given below:

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;
}