## 10167 - Birthday Cake

Moderator: Board moderators

benetin
New poster
Posts: 2
Joined: Thu Feb 13, 2003 11:36 pm

### 10167 - Birthday Cake

--- 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??

SDiZ
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:

### 10167 Birthday Cake

I got WA..
any one have good test case for this question?

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

Try not to use doubles.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

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

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm
Can anyone explain how to solve this problem?

Thanks alot

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
I did it by trying random lines.

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 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?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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.

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 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?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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.

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 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

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 10167 - Birthday Cake

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

amacfie
New poster
Posts: 2
Joined: Tue Dec 23, 2008 3:36 am

### Re: 10167 - Birthday Cake

why is randomized faster than linear iteration?

JINX
New poster
Posts: 3
Joined: Sat Jul 19, 2008 3:36 pm

### Re: 10167 - Birthday Cake

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[100];

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

diego_engcomp
New poster
Posts: 9
Joined: Sat Jul 18, 2009 1:18 am

### Re: 10167 - Birthday Cake

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.