Time Limit: 5 Sec??Memory Limit: 64 MB
Submit: 489??Solved: 384
[Submit][Status][Discuss]

Description

奶牛們最近從著名的奶牛玩具制造商Tycow那里，買了一套仿真版彩彈游戲設(shè)備（類乎于真人版CS）。 Bessie把她們玩游戲草坪劃成了N * N(1 <= N<= 100)單位的矩陣，同時(shí)列出了她的 K (1 <= K <= 100,000)個(gè)對(duì)手在草地上的位置。然后她拿著這張表來(lái)找你，希望你能幫她計(jì)算一個(gè)數(shù)據(jù)。 在這個(gè)游戲中，奶牛可以用一把彈珠槍向8個(gè)方向中的任意一個(gè)射出子彈。8個(gè)方向分別是：正北，正南，正東，正西，以及夾在這4個(gè)正方向之間的45°角:東北，東南，西北，西南方向。 Bessie望你告訴她，如果她想站在一個(gè)可以射到她的所有對(duì)手的格子上，那么她有多少種選擇。當(dāng)然，貝茜可以跟她的某一個(gè)對(duì)手站在同一個(gè)格子上，并且在這種情況下，你可以認(rèn)為貝茜能射到跟她站在同一格子里的對(duì)手。

Input

* 第1行: 2個(gè)用空格隔開的整數(shù)：N和K

* 第2..K+1行: 第i+1行用2個(gè)以空格隔開整數(shù)R_i和C_i，描述了第i頭奶牛的位置，表示她站在第R_i行，第C_i列

Output

* 第1行: 輸出1個(gè)整數(shù)，表示如果Bessie可以選擇的格子的數(shù)目。

Sample Input

4 3
2 1
2 3
4 1

輸入說(shuō)明:

牧場(chǎng)被劃分成了4行4列。Bessie的站位必須保證她能射到站在(2,1)，(2,3)

以及(4,1)的奶牛：

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

Sample Output

5

輸出說(shuō)明:

Bessie可以選擇站在以下格子中的任意一個(gè)：(2,1)，(2,3)，(3,2)，(4,1)，
以及(4,3)。下右圖中，Bessie與其他牛共同占有的格子被標(biāo)記為'*'：
. . . . . . . .
B . B . ---\ * . * .
. B . . ---/ . B . .
B . B . * . B .

思路

顯然，對(duì)于每個(gè)位置，四個(gè)方向是不相交的； 所有就可以預(yù)處理出hs,ls,hls,lhs的值，然后根據(jù)這個(gè)判斷每個(gè)點(diǎn)合不合適；

代碼實(shí)現(xiàn)

1 #include<cstdio> 2 const int maxn=110; 3 int n,k,ans; 4 int map[maxn][maxn]; 5 int hs[maxn],ls[maxn],hls[maxn<<1],lhs[maxn<<1]; 6 int main(){ 7 scanf("%d%d",&n,&k); 8 int x,y; 9 for(int i=1;i<=k;i++){ 10 scanf("%d%d",&x,&y); 11 map[x][y]++; 12 hs[x]+=map[x][y]; 13 ls[y]+=map[x][y]; 14 hls[n-x+y]+=map[x][y]; 15 lhs[x+y-1]+=map[x][y]; 16 } 17 for(int i=1;i<=n;i++) 18 for(int j=1;j<=n;j++) 19 if(hs[i]+ls[j]+hls[n-i+j]+lhs[i+j-1]-3*map[i][j]==k) ans++; 20 printf("%d\n",ans); 21 return 0; 22 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/J-william/p/8058193.html

總結(jié)

以上是生活随笔為你收集整理的[Usaco2007 Oct] Super Paintball超级弹珠的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。