uva10167 容易的生成测试法

uva10167 简单的生成测试法

题意：有一块蛋糕，上面有2N个樱桃，问如何划分蛋糕保证两块大小一样且上面的樱桃也一样多。输出A和B，即代表Ax+By=0的一条切割线，这个题好在给定了A和B的范围是【-500,500】，所以枚举所有的A和B总共也就1000*1000的复杂度，是可以接受的，所以采用了枚举生成切割线，然后判断切割线两边的樱桃数是否一样多就没有什么难度了。

有几个地方要注意

1、初中数学就应该学过如何判断点和直线的位置关系了，将点的坐标（x，y）代入直线方程Ax+By，若>0，则点在直线上方，<0在下方，=0则在直线上，因为题目要求樱桃不允许位于切割线上，所以出现=0的情况就要去掉。

2、A或B有一个是0的时候不需要再枚举其它的值，因为有一个是0就代表着这条切割线是x轴或y轴，也算是一点剪枝吧

3、题目很简单，细心一点一定一次AC！

代码如下

#include<iostream>
using namespace std;

int N;

struct coordinate
{
	int x,y;
};

bool divide(int A,int B,coordinate ch[])
{
	int count1=0,count2=0;
	for (int i=0;i<2*N;i++)
	{
		if (A*ch[i].x+B*ch[i].y>0) count1++;
		else if (A*ch[i].x+B*ch[i].y<0) count2++;
		else return false;
	}
	if (count1==count2) return true;
	else return false;
}
int main()
{
	while (cin>>N&&N)
	{
		coordinate* cherry=new coordinate[2*N];
		for (int i=0;i<2*N;i++)
		{
			cin>>cherry[i].x>>cherry[i].y;
		}
		if (divide(0,1,cherry)) 
		{
			cout<<"0 1"<<endl;
			delete[] cherry;
			continue;
		}
		if (divide(1,0,cherry))
		{
			cout<<"1 0"<<endl;
			delete[] cherry;
			continue;
		}
		bool flag=0;
		for (int A=1;A<=500;A++)
		{
			for (int B=1;B<=500;B++)
			{
				if (divide(A,B,cherry))
				{
					cout<<A<<" "<<B<<endl;
					flag=1;
					break;
				}
				else if (divide(A,-B,cherry))
				{
					cout<<A<<" "<<-B<<endl;
					flag=1;
					break;
				}
			}
			if (flag==1) break;
		}
		delete[] cherry;
	}
	return 0;
}