题目描述 Description
奶牛们最近从著名的奶牛玩具制造商Tycow那里,买了一套仿真版彩蛋游戏设备。Bessie把她们玩游戏的草坪划成了N*N单位的矩阵,同时列出了她的K个对手在草地上的位置。然后她拿着这张表来找你,希望你能帮她计算一个数据。
在这个游戏中,奶牛可以用一把弹珠枪向8个方向(正东、正南、正西、正北、正东北、正东南、正西北、正西南)中的任意一个方向发射子弹。Bessie希望你告诉她,如果她想站在一个可以射到所有对手的格子上,那么她有多少种选择。当然,Bessie可以跟某一个对手站在同一个格子上,在这种情况下,Bessie也能射到这个对手。
第一行:两个用空格隔开的整数:N K
第二至第K+1行:第i+1行有两个以空格隔开的整数R-i和C-i,描述第i头奶牛的位置,表示她站在第R-i行,C-i列。
仅一行:输出一个整数,表示Bessie可以选择的格子数量。
4 3
2 1
2 3
4 1
5
数据范围
1<=N<=500
1<=K<=100 000
样例说明
Bessie可以选择站在一下格子中的任意一个:(2,1),(2,3),(3,2),(4,4),(4,3).下右图中,Bessie与其他奶牛共同占有的格子被标记为“*”
. . . . . . . .
B . B . =======> * . * .
. B . . =======> . B . .
B . B . * . B .
提示:
使用穷举即可。
解题思路
题目告诉我穷举即可,然后我就果断穷举了,这个题涉及到一些关于斜率的东西,其实就是那个斜率公式
(y2-y1)/(x2-x1)=±1,化简一下其实就是x+y那条斜率,x-y那条斜率上的点加一,横轴竖轴加一
枚举节点,然后把经过该点的横轴竖轴斜边都加起来,减去本身乘3,防止重复计算
program SuperBall;
var dt:array[..,..] of longint;
n,k,i,a,b:Longint;
z1,z2,x,y:array[-..] of longint;
begin
read(n,k);
for i:= to k do
begin
read(a,b);
inc(x[a]);
inc(y[b]);
inc(z1[a+b]);
inc(z2[a-b]);
end;
for i:= to do
for j:= to do
begin
if x[i]+y[j]+z1[i+j]+z[i-j]-*dt[i,j]=k then inc(ans);
end;
writeln(ans);
end.