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

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

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 339  Solved: 264

[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

题解:既然正着枚举点的合法性显然比较扯。。。那么何不反其道而行之呢,嗯哼,懂我的意思吧(HansBug:就算不懂看我程序也该懂了吧)

 1 /**************************************************************
 2     Problem: 1709
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:4 ms
 7     Memory:304 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n,x,y:longint;
12    a,b:array[0..100,0..100] of longint;
13 begin
14      readln(n,m);l:=0;
15      fillchar(a,sizeof(a),0);
16      fillchar(b,sizeof(b),0);
17      for i:=1 to m do
18          begin
19               readln(j,k);
20               l:=l+1-a[j,k];
21               a[j,k]:=1;
22          end;
23      m:=l;l:=0;
24      for i:=1 to n do
25          for j:=1 to n do
26              if a[i,j]=1 then
27                 begin
28                      x:=i-1;y:=j;
29                      while x>0 do
30                            begin
31                                 inc(b[x,y]);
32                                 dec(x);
33                            end;
34                      x:=i+1;y:=j;
35                      while x<=n do
36                            begin
37                                 inc(b[x,y]);
38                                 inc(x);
39                            end;
40                      x:=i;y:=j-1;
41                      while y>0 do
42                            begin
43                                 inc(b[x,y]);
44                                 dec(y);
45                            end;
46                      x:=i;y:=j+1;
47                      while y<=n do
48                            begin
49                                 inc(b[x,y]);
50                                 inc(y);
51                            end;
52                      x:=i-1;y:=j-1;
53                      while (x>0) and (y>0) do
54                            begin
55                                 inc(b[x,y]);
56                                 dec(x);dec(y);
57                            end;
58                      x:=i+1;y:=j-1;
59                      while (x<=n) and (y>0) do
60                            begin
61                                 inc(b[x,y]);
62                                 inc(x);dec(y);
63                            end;
64                      x:=i-1;y:=j+1;
65                      while (x>0) and (y<=n) do
66                            begin
67                                 inc(b[x,y]);
68                                 dec(x);inc(y);
69                            end;
70                      x:=i+1;y:=j+1;
71                      while (x<=n) and (y<=n) do
72                            begin
73                                 inc(b[x,y]);
74                                 inc(x);inc(y);
75                            end;
76                      inc(b[i,j]);
77                 end;
78      l:=0;
79      for i:=1 to n do
80          for j:=1 to n do
81              if b[i,j]=m then inc(l);
82      writeln(l);
83      readln;
84 end.            

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1734: [Usaco2005 feb]Aggressive cows 愤怒的牛

1734: [Usaco2005 feb]Aggressive cows 愤怒的牛 Time Limit: 5 Sec  Memory Limit: 64 MB...

29970
来自专栏HansBug's Lab

1593: [Usaco2008 Feb]Hotel 旅馆

1593: [Usaco2008 Feb]Hotel 旅馆 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 39...

32240
来自专栏HansBug's Lab

3401: [Usaco2009 Mar]Look Up 仰望

3401: [Usaco2009 Mar]Look Up 仰望 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: ...

35070
来自专栏CreateAMind

autoware 代码阅读 sensor

ROS driver to parse NMEA strings and publish standard ROS NavSat message types. ...

25820
来自专栏HansBug's Lab

1688: [Usaco2005 Open]Disease Manangement 疾病管理

1688: [Usaco2005 Open]Disease Manangement 疾病管理 Time Limit: 5 Sec  Memory Limit: ...

30750
来自专栏HansBug's Lab

1639: [Usaco2007 Mar]Monthly Expense 月度开支

1639: [Usaco2007 Mar]Monthly Expense 月度开支 Time Limit: 5 Sec  Memory Limit: 64 MB...

33160
来自专栏HansBug's Lab

1634: [Usaco2007 Jan]Protecting the Flowers 护花

1634: [Usaco2007 Jan]Protecting the Flowers 护花 Time Limit: 5 Sec  Memory Limit:...

33180
来自专栏HansBug's Lab

1578: [Usaco2009 Feb]Stock Market 股票市场

1578: [Usaco2009 Feb]Stock Market 股票市场 Time Limit: 10 Sec  Memory Limit: 64 MB S...

277110
来自专栏HansBug's Lab

1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机

1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机 Time Limit: 5 Sec  Memory ...

343110
来自专栏智能计算时代

Most Influential Data Science Accounts on Twitter

The Data Science Influencers: The Tops in Terms of "Insider Score" According to ...

27080

扫码关注云+社区

领取腾讯云代金券