[Usaco2007 Oct]Super Paintball超级弹珠

Description

奶牛们最近从著名的奶牛玩具制造商Tycow那里，买了一套仿真版彩弹游戏设备（类乎于真人版CS）。 Bessie把她们玩游戏草坪划成了N * N(1 <= N<= 100)单位的矩阵，同时列出了她的 K (1 <= K <= 100,000)个对手在草地上的位置。然后她拿着这张表来找你，希望你能帮她计算一个数据。在这个游戏中，奶牛可以用一把弹珠枪向8个方向中的任意一个射出子弹。8个方向分别是：正北，正南，正东，正西，以及夹在这4个正方向之间的45°角:东北，东南，西北，西南方向。 Bessie望你告诉她，如果她想站在一个可以射到她的所有对手的格子上，那么她有多少种选择。当然，贝茜可以跟她的某一个对手站在同一个格子上，并且在这种情况下，你可以认为贝茜能射到跟她站在同一格子里的对手。

Input

* 第1行: 2个用空格隔开的整数：N和K

* 第2..K+1行: 第i+1行用2个以空格隔开整数R_i和C_i，描述了第i头奶牛的位置，表示她站在第R_i行，第C_i列

Output

* 第1行: 输出1个整数，表示如果Bessie可以选择的格子的数目。

Sample Input

4 3
2 1
2 3
4 1

输入说明:

牧场被划分成了4行4列。Bessie的站位必须保证她能射到站在(2,1)，(2,3)

以及(4,1)的奶牛：

. . . .
C . C .
. . . . <— 奶牛们的位置
C . . .

Sample Output

输出说明:

Bessie可以选择站在以下格子中的任意一个：(2,1)，(2,3)，(3,2)，(4,1)，
以及(4,3)。下右图中，Bessie与其他牛共同占有的格子被标记为’*’：
. . . . . . . .
B . B . —\ * . * .
. B . . —/ . B . .
B . B . * . B .

题解

用h[i],s[i],z[i],t[i]表示每行/列，两个方向的对角线上的对手数

注意考虑可以和对手站在一起

题解：爆搜

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define N 105

 using namespace std;

 int n,m,x,y,now,ans;

 int cnt[N][N];

 int main()

 {

     scanf("%d%d",&n,&m);

     for (int i=;i<=m;++i)

     {

         scanf("%d%d",&x,&y);

         ++cnt[x][y];

     }

     for (int i=;i<=n;++i)

         for (int j=;j<=n;++j)

         {

             now=cnt[i][j];

             for (int k=i-;k>=;--k) now+=cnt[k][j];

             for (int k=i+;k<=n;++k) now+=cnt[k][j];

             for (int k=j-;k>=;--k) now+=cnt[i][k];

             for (int k=j+;k<=n;++k) now+=cnt[i][k];

             x=i-,y=j-;

             while (x>&&y>) now+=cnt[x][y],--x,--y;

             x=i+,y=j+;

             while (x<=n&&y<=n) now+=cnt[x][y],++x,++y;

             x=i+,y=j-;

             while (x<=n&&y>) now+=cnt[x][y],++x,--y;

             x=i-,y=j+;

             while (x>&&y<=n) now+=cnt[x][y],--x,++y;

             if (now==m) ++ans;

         }

     printf("%d\n",ans);

 }

弹珠

bzoj1709 [Usaco2007 Oct]Super Paintball超级弹珠 暴力