Bzoj1709 超级弹珠superpaintball

Posted by yjjr's blog on February 6, 2018

标签:模拟

Description

奶牛们最近从著名的奶牛玩具制造商Tycow那里,买了一套仿真版彩弹游戏设备(类乎于真人版CS)。 Bessie把她们玩游戏草坪划成了N * N(1 <= N<= 100)单位的矩阵,同时列出了她的 K (1 <= K <=100,000)个对手在草地上的位置。然后她拿着这张表来找你,希望你能帮她计算一个数据。在这个游戏中,奶牛可以用一把弹珠枪向8个方向中的任意一个射出子弹。8个方向分别是:正北,正南,正东,正西,以及夹在这4个正方向之间的45°:东北,东南,西北,西南方向。 Bessie望你告诉她,如果她想站在一个可以射到她的所有对手的格子上,那么她有多少种选择。当然,贝茜可以跟她的某一个对手站在同一个格子上,并且在这种情况下,你可以认为贝茜能射到跟她站在同一格子里的对手。

Input

*1: 2个用空格隔开的整数:NK

*2..K+1:i+1行用2个以空格隔开整数R_iC_i,描述了第i头奶牛的位置,表示她站在第R_i行,第C_i

Output

*1:输出1个整数,表示如果Bessie可以选择的格子的数目。

Sample Input

4 3
2 1
2 3
4 1

输入说明:

牧场被划分成了44列。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 .

 

分析:将每个奶牛的的两条对角线与平行于边界的线打上标记,最后统计每个点的标记个数,如果和奶牛的数量相等,那么答案计数++

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=100005,maxm=210;
int s[maxm][maxm]={0},x[maxn],y[maxn],ans=0,n,k;
inline void work(int t)
{
	rep(i,1,n)s[x[t]][i]++;
	rep(i,1,n)s[i][y[t]]++;
	rep(i,-n+1,n-1)if(x[t]+i>=1&&x[t]+i<=n&&y[t]+i>=1&&y[t]+i<=n)s[x[t]+i][y[t]+i]++; 
	rep(i,-n+1,n-1)if(x[t]-i>=1&&x[t]-i<=n&&y[t]+i>=1&&y[t]+i<=n)s[x[t]-i][y[t]+i]++;
	s[x[t]][y[t]]-=3;
}

int main()
{
    n=read(),k=read();
    rep(i,1,k){x[i]=read(),y[i]=read();work(i);}
    rep(i,1,n)
    	rep(j,1,n)
    	    if(s[i][j]==k)ans++;
    /*rep(i,1,n){
        rep(j,1,n)cout<<s[i][j]<<' ';
        cout<<endl;
    }*/
    cout<<ans<<endl;
	return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr