10167 - Birthday Cake

[benetin]

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

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

[daveon]

Hi,

Try not to use doubles.

[daveon]

Hi,

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

[cpphamza]

Can anyone explain how to solve this problem?

Thanks alot

[Darko]

I did it by trying random lines.

[cpphamza]

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]

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]

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]

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]

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]

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.

[amacfie]

why is randomized faster than linear iteration?

[JINX]

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]

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.