首页 > 代码库 > BZOJ1709: [Usaco2007 Oct]Super Paintball超级弹珠

BZOJ1709: [Usaco2007 Oct]Super Paintball超级弹珠

2024-07-27 17:39:04   217人阅读

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

4 3
2 1
2 3
4 1

输入说明:

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

以及(4,1)的奶牛：

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

Sample Output

5

输出说明:

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

HINT

Source

Gold

题解：

暴力枚举每个点肯定是不行的。

反过来想一想，只要我们对每个敌人能被打到的点标记一下，最后看哪个点被标记过m次即可

代码：

 1 #include<cstdio> 2  3 #include<cstdlib> 4  5 #include<cmath> 6  7 #include<cstring> 8  9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 50026 27 #define maxm 500+10028 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define mod 100000000744 45 using namespace std;46 47 inline int read()48 49 {50 51     int x=0,f=1;char ch=getchar();52 53     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}54 55     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}56 57     return x*f;58 59 }60 int n,m,ans,d[maxn][maxn];61 62 int main()63 64 {65 66     freopen("input.txt","r",stdin);67 68     freopen("output.txt","w",stdout);69 70     n=read();m=read();71     for1(i,m)72     {73         int x=read(),y=read();d[x][y]++;74         for1(i,n)if(i!=y)d[x][i]++;75         for1(i,n)if(i!=x)d[i][y]++;76         for1(i,n)if(i!=x)d[i][x+y-i]++;77         for1(i,n)if(i!=x)d[i][max(0,y-x+i)]++;78     }79     for1(i,n)for1(j,n)if(d[i][j]==m)ans++;80     printf("%d\n",ans);81 82     return 0;83 84 }
View Code

 

BZOJ1709: [Usaco2007 Oct]Super Paintball超级弹珠


联系
我们