Page 1 of 2

### 10167 - Birthday Cake

Posted: Tue Feb 18, 2003 8:42 am
--- Note: the coordinate of a cherry (x , y) are two integers. You must give the line as form two integers A,B(stands for Ax+By=0) each number mustn't in [-500,500].

What does that mean by "mustn't in[-500,500]", while the sample output is 0,1??

### 10167 Birthday Cake

Posted: Fri Aug 05, 2005 12:22 pm
I got WA..
any one have good test case for this question?

Posted: Sat Aug 19, 2006 3:37 pm
Hi,

Try not to use doubles.

Posted: Sat Aug 19, 2006 3:38 pm
Hi,

It actually means, A and B are between -500 and 500 inclusive.

Posted: Thu Oct 19, 2006 11:07 pm
Can anyone explain how to solve this problem?

Thanks alot

Posted: Thu Oct 19, 2006 11:22 pm
I did it by trying random lines.

Posted: Fri Oct 20, 2006 4:37 pm
do you mean you randomly choose A then randomly choose B and check if the same number of points lie on each of the line sides?

I think this problem has some mathematical approach (looking at the very small times it has been solved in), any ideas?

Posted: Fri Oct 20, 2006 5:13 pm
Yes, that's what I mean.

I was thinking about sorting them by angle and go looking for a line that splits them in two - but it sounded too complicated, so I tried random. And it worked (there are only 50 points on a 1000x1000 grid). My time is 0.014 in Java.

Posted: Fri Oct 20, 2006 9:21 pm
Well I've tried the random approach as follows:

while(true){
-randomly generate A, B. That is O(1)
-divide the points in two sets where each set lies in one side of the line Ax+BY=0. That is O(n)
-if both sets has the same size break
}

However the soltion also times out! do you make any further enhancements?

Posted: Fri Oct 20, 2006 9:58 pm
That's exactly what I do.
I am using integers and built-in random function. How do you look for random numbers? And are they in the right range, [-500,500]?
Btw, that "if both sets same size, break" part is wrong, should be "if both sets are of size n, break". Just check that you really break.

Posted: Fri Oct 20, 2006 10:25 pm
Got AC using your random approach (I had a bug in intializing an array ).
Btw, that "if both sets same size, break" part is wrong, should be "if both sets are of size n, break". Just check that you really break.
Funny thing I got AC using my wrong condition, I think there wasn't a testcase for that!

I still can't imagine that a problem setter intended such a solution for the problem

### Re: 10167 - Birthday Cake

Posted: Wed May 07, 2008 5:01 am
I solved this using a Divide-and-conquer approach. I got the idea from problem 10077 - The Stern-Brocot number system. However, a brute force algorithm will also run on time.

### Re: 10167 - Birthday Cake

Posted: Tue Jan 06, 2009 2:00 am
why is randomized faster than linear iteration?

### Re: 10167 - Birthday Cake

Posted: Sun Aug 23, 2009 3:28 pm
Here is my code that uses the random method, but it is slow and cann't get an AC.
Needs some help.
Thanks.

Code: Select all

``````#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int N;

struct Point
{
int x,y;
};

Point p;

void Process()
{
int A,B;
srand ( time(NULL) );
while (true)
{
A = rand()*1000/RAND_MAX-500;
B = rand()*500/RAND_MAX;
//cout<<A<<' '<<B<<endl;
int count1 = 0;
int count2 = 0;
for (int i=0;i<2*N;i++)
{
if (A*p[i].x+B*p[i].y>0)
{
count1++;
}
// 			else if(A*p[i].x+B*p[i].y<0)
// 			{
// 				count2 ++;
// 			}
}
if (count1*2==N)
{
break;
}
}
cout<<A<<' '<<B<<endl;
}

int main()
{
cin>>N;
while (N)
{
for (int i=0;i<N*2;i++)
{
cin>>p[i].x>>p[i].y;
}
Process();
cin>>N;
}
return 0;
}``````

### Re: 10167 - Birthday Cake

Posted: Thu Dec 17, 2009 3:42 pm
JINX, I used the same ideia than you and got AC. I'm not sure if your way to generate the random numbers is correct. I think a more easy way is:

Code: Select all

``````a=-500+(rand()%1001);
b=-500+(rand()%1001);
``````
And I think that the break condition should be:

Code: Select all

``````if(count1==n && count2==n)
break;
``````
I hope it helps. Sorry for my english.