## 10136 - Chocolate Chip Cookies

Moderator: Board moderators

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

### 10136 - Chocolate Chip Cookies

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

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
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
New poster
Posts: 11
Joined: Wed Jun 04, 2008 1:39 pm

### Re: 10136 - Chocolate Chip Cookies

@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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

### Re: 10136 - Chocolate Chip Cookies

@bourne

If only I had as much free time as I did in college...

armansuleimenov
New poster
Posts: 15
Joined: Tue Sep 25, 2007 3:07 am
Location: Astana, Kazakhstan
Contact:

### Re: 10136 - Chocolate Chip Cookies

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

``````