首页 > ACM题库 > HDU-杭电 > HDU 1152 Brownie Points I[解题报告] C++
2013
12-03

HDU 1152 Brownie Points I[解题报告] C++

Brownie Points I

问题描述 :

Stan and Ollie play the game of Odd Brownie Points. Some brownie points are located in the plane, at integer coordinates. Stan plays first and places a vertical line in the plane. The line must go through a brownie point and may cross many (with the same x-coordinate). Then Ollie places a horizontal line that must cross a brownie point already crossed by the vertical line.
Those lines divide the plane into four quadrants. The quadrant containing points with arbitrarily large positive coordinates is the top-right quadrant.

The players score according to the number of brownie points in the quadrants. If a brownie point is crossed by a line, it doesn’t count. Stan gets a point for each (uncrossed) brownie point in the top-right and bottom-left quadrants. Ollie gets a point for each (uncrossed) brownie point in the top-left and bottom-right quadrants.

Your task is to compute the scores of Stan and Ollie given the point through which they draw their lines.

输入:

Input contains a number of test cases. The data of each test case appear on a sequence of input lines. The first line of each test case contains a positive odd integer 1 < n < 200000 which is the number of brownie points. Each of the following n lines contains two integers, the horizontal (x) and vertical (y) coordinates of a brownie point. No two brownie points occupy the same place. The input ends with a line containing 0 (instead of the n of a test).

输出:

For each test case of input, print a line with two numbers separated by a single space. The first number is Stan’s score, the second is the score of Ollie when their lines cross the point whose coordinates are given at the center of the input sequence of points for this case.

样例输入:

11
3 2
3 3
3 4
3 6
2 -2
1 -3
0 0
-3 -3
-3 -2
-3 -4
3 -7
0

样例输出:

6 3

点击打开链接

分析:

输入一个非负的奇数,当输入到最中间的数时,画一条水平线和竖直线,判断其他点的位置,注意不包括线上的点。。

#include"stdio.h"
#include"string.h"
int x[200001],y[200001];
int main()
{
	int i;
	int n;
	int a,b,t;
	while(scanf("%d",&n)!=-1&&n)
	{
		for(i=0;i<(n+1)/2;i++)
			scanf("%d%d",&x[i],&y[i]);
		a=b=0;
		t=(n+1)/2-1;
		for(i=0;i<t;i++)
		{
			if(x[i]>x[t])
			{
				if(y[i]>y[t])a++;
				else if(y[i]<y[t])b++;
			}
			else if(x[i]<x[t])
			{
				if(y[i]<y[t])a++;
				else if(y[i]>y[t])b++;
			}
		}
		for(i=0;i<t;i++)
		{
			scanf("%d%d",&x[i],&y[i]);
			if(x[i]>x[t])
			{
				if(y[i]>y[t])a++;
				else if(y[i]<y[t])b++;
			}
			else if(x[i]<x[t])
			{
				if(y[i]<y[t])a++;
				else if(y[i]>y[t])b++;
			}
		}
		printf("%d %d\n",a,b);
	}
	return 0;
}


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。