1709: [Usaco2007 Oct]Super Paintball超级弹珠
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 324 Solved: 253
[Submit][Status]
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
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 .
HINT
Source
题解:
暴力枚举每个点肯定是不行的。
反过来想一想,只要我们对每个敌人能被打到的点标记一下,最后看哪个点被标记过m次即可
代码:
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<queue> #include<string> #define inf 1000000000 #define maxn 500 #define maxm 500+100 #define eps 1e-10 #define ll long long #define pa pair<int,int> #define for0(i,n) for(int i=0;i<=(n);i++) #define for1(i,n) for(int i=1;i<=(n);i++) #define for2(i,x,y) for(int i=(x);i<=(y);i++) #define for3(i,x,y) for(int i=(x);i>=(y);i--) #define mod 1000000007 using namespace std; inline int read() { int x=,f=;char ch=getchar(); while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();} while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();} return x*f; }
int n,m,ans,d[maxn][maxn]; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();m=read();
for1(i,m)
{
int x=read(),y=read();d[x][y]++;
for1(i,n)if(i!=y)d[x][i]++;
for1(i,n)if(i!=x)d[i][y]++;
for1(i,n)if(i!=x)d[i][x+y-i]++;
for1(i,n)if(i!=x)d[i][max(,y-x+i)]++;
}
for1(i,n)for1(j,n)if(d[i][j]==m)ans++;
printf("%d\n",ans); return ; }