Brownie Points I

code

4 年前

Brownie Points I

时间： 1ms 内存：128M

描述：

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.

输入：

输出：

示例输入：

示例输出：

6 3

提示：

参考答案（内存最优[912]）：

// PR, May 14, 2005

// 1 2
// 2 4  6
//   6  9 12
//     12 16 20
//        20 25 30
//           30 36 42
//              42 49 56

// Set 1 to 0, whatever is 2 then 4 has to be 0 because of the first
// two raws. 4 and 9 have to be the same bacause of raws 2 and 3
// and so on for all squares.

// find smallest binary magic string of lenght p-1 where p is prime 
// Set the diagonal of the magic square to 0's the rest to 1's.
// Indices that are quadratic residues mod p appear on the diagonal
// and p has the same number od residues and non-residues unless
// p is 2.
// there are 4 magic strings of any length except 2.

// The string must be a palindrom or its reverse is its complement.

#include <stdio.h>
#include <assert.h>
#include <math.h>

#define MAXP 100000

int isPrime(int a) {
  if (a < 2) return 0;
  for (int i = 2; i <= sqrt((double)a); i++) if (!(a%i)) return 0;
  return 1;
}

char A[MAXP+10];

int main () {
  while (1) {
    int p;
    scanf("%d",&p);
    if (!p) break;
    assert(isPrime(p) && p <= MAXP);
    if (p == 2) { printf("Impossible\n"); continue; }
    for (int i=1;i<p;i++) A[i] = '1';
    for (unsigned long long i=1;i<p;i++) 
      A[(i*i)%p]='0';
    for (int i=1;i<p;i++)
      printf("%c",A[i]);
    printf("\n");
  }
}

参考答案（时间最优[8]）：

//  PR, meant to be immediate

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

using namespace std;

#define MAXN 200000

int main () {
  int n;
  int x[MAXN], y[MAXN];
  while (1) {
    scanf("%d",&n);
    if (!n) break;
    assert(0 < n && n%2 && n <= MAXN);
    int nn = (n-1)/2;
    int xb, yb;
    for(int i=0;i<n;i++) {
      scanf("%d%d",&x[i],&y[i]);
      if (i == nn) {
	xb = x[i]; yb = y[i];
      }
    }
    int ss = 0, os = 0;
    for (int i = 0; i<n; i++) {
      if (x[i] < xb && y[i] < yb || x[i] > xb && y[i] > yb) ss++;
      if (x[i] < xb && y[i] > yb || x[i] > xb && y[i] < yb) os++;
    }
    printf("%d %d\n",ss,os);
  }
  return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。