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

补充：软件开发 , C++ ,