uva10167 简单的生成测试法 - c++编程基础

题意：有一块蛋糕，上面有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  
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"<