BZOJ1709 超級彈珠SuperPaintball

标簽:模拟

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 .

分析：将每個奶牛的的兩條對角線與平行于邊界的線打上标記，最後統計每個點的标記個數，如果和奶牛的數量相等，那麼答案計數++

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;
}