uva 10167 Birthday Cake

Background

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 in the range [-500,500]. Cherries are not allowed lying on the beeline. For each dataset there is at least one solution.

Input

Output

Sample Input

2
-20 20
-30 20
-10 -50
10 -5
0

Sample Output

0 1

题目大意：有一块蛋糕（圆形），蛋糕上有樱桃，要求切一刀，使得分割线过圆心并且被分割的两块上的樱桃数量一样多。

解题思路：利用关系式 Ax + By = 0，枚举所有可能的 A 和 B，统计在直线上下的樱桃数是否相等。

#include<stdio.h>
struct cherry {
	int x;
	int y;
};
int main() {
	int m;
	while (scanf("%d", &m) == 1, m) {
		cherry c[5500];
		for (int i = 0; i < 2 * m; i++) {
			scanf("%d", &c[i].x);
			scanf("%d", &c[i].y);
		}
		int cnt1, cnt2, i, j;
		for (i = -500; i <= 500; i++) {
			for (j = -500; j <= 500; j++) {
				if (i == 0 && j == 0) {continue;}
				cnt1 = 0; cnt2 = 0;
				for (int k = 0; k < 2 * m; k++) {
					if (i * c[k].x + j * c[k].y < 0) {   //在分割线下方的樱桃
						cnt1++;
						continue;
					}
					else if (i * c[k].x + j * c[k].y > 0) {   //在分割线上方的樱桃
						cnt2++;
						continue;
					}
					else break;   //切到了樱桃，跳出循环
				}

				if (cnt1 == m && cnt2 == m) {  //如果分割线上下的樱桃数相等，且等于总樱桃数的一半，切割成功。
					printf("%d %d\n", i, j);
					break;
				}
			}
			if (cnt1 == m && cnt2 == m) {
				break;
			}
		}
	}
	return 0;
}

uva 10167 Birthday Cake（暴力/枚举）