UVA10167 Birthday Cake【暴力】

本文主要是介绍UVA10167 Birthday Cake【暴力】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Lucy and Lily are twins. Today is their birthday. Mother buys a birthday cake for them. Now we put the cake onto a Descartes coordinate. Its center is at (0, 0), and the cake’s length of radius is 100.
    There are 2N (N is a integer, 1 ≤ N ≤ 50) cherries on the cake. Mother wants to cut the cake into two halves with a knife (of course a beeline). The twins would like to be treated fairly, that means, the shape of the two halves must be the same (that means the beeline must go through the center of the cake) , and each half must have N cherrie(s). Can you help her?
    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]. Cherries are not allowed lying on the beeline. For each dataset there is at least one solution.
在这里插入图片描述
Input
The input file contains several scenarios. Each of them consists of 2 parts:
    The first part consists of a line with a number N, the second part consists of 2N lines, each line has two number, meaning (x, y). There is only one space between two border numbers. The input file is ended with N = 0.
Output
For each scenario, print a line containing two numbers A and B. There should be a space between them. If there are many solutions, you can only print one of them.
Sample Input
2
-20 20
-30 20
-10 -50
10 -5
0
Sample Output
0 1

问题链接：UVA10167 Birthday Cake
问题简述：
给定2N 个点，求A和B为多少时，直线Ax+By=0 把点分成相等的两部分。
问题分析：
本题可以用暴力法来解决。把点带入直线方程Ax+By=0，那么大于0的是一边，小于0的是另外一边，枚举A和B，统计一下就可以。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++程序如下：

/* UVA10167 Birthday Cake */#include <iostream>using namespace std;const int LEFT = -500, RIGHT = 500;
const int N = 50;
int x[N * 2], y[N * 2];int main()
{int n;while(~scanf("%d", &n) && n) {n *= 2;for(int i = 0; i < n; i++)scanf("%d%d", &x[i], &y[i]);bool flag = true;for(int a = LEFT; a <= RIGHT && flag; a++)for(int b = LEFT; b <= RIGHT ; b++) {if(a==0 && b==0 ) continue;int i, cnt = 0;     // 统计满足AX+BY>0的点数目for(i = 0; i < n; i++) {if(a * x[i] + b * y[i] > 0) ++cnt;else if(a * x[i] + b * y[i] == 0) break;}if( i < n) continue;if(cnt == n / 2) {printf("%d %d\n", a, b);flag = false;break;}}}return 0;
}