## Super Paintball [Aram Shatakhtsyan, 2007]

The cows have purchased a Super Paintball Deluxe game set from Tycow, the cow-toy manufacturer. Bessie, knowing you can help, has partitioned the pasture into a set of N x N unit squares (1 <= N <= 100) and compiled a list of the K (1 <= K <= 100,000) locations (1 <= R_i <= N; 1 <= C_i <= N) of every one of her opponents in the Paintball game. This paintball game features a paintball gun that can shoot paintballs in any of eight directions: north, south, east, west, and the diagonals that split those directions exactly (northeast, southeast, northwest, southwest). Bessie wants you to tell her the total number of squares she can occupy and still be able to shoot all of her opponents (she can even shoot them if she shares the same square as they occupy!). PROBLEM NAME: paint2 INPUT FORMAT: * Line 1: Two space-separated integers: N and K * Lines 2..K+1: Line i+1 describes cow i's location with two space-separated integers: R_i and C_i SAMPLE INPUT (file paint2.in): 4 3 2 1 2 3 4 1 INPUT DETAILS: The pasture has 4 rows and 4 columns. Bessie needs to shoot cows at (2,1), (2,3), and (4,1): . . . . C . C . . . . . <--- Cow locations C . . . OUTPUT FORMAT: * Line 1: A single integer that tells how many different locations Bessie may occupy if she is to be able to shoot any cow according to the shooting rules. SAMPLE OUTPUT (file paint2.out): 5 OUTPUT DETAILS: Bessie can occupy any of these cells: (2,1), (2,3), (3,2), (4,1), and (4,3). The diagram below notates possibly shared spaces by '*': . . . . . . . . B . B . ---\ * . * . . B . . ---/ . B . . B . B . * . B . Potential Bessie Bessie & Cows Locations
ქართული თარგმანი არ არის დამატებული

## USA's Stephen Carlson wrote a Java solution:

```import java.io.*;
import java.util.*;

public class paint2 {
public static void main(String[] args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedWriter(new
FileWriter("paint2.out")));
int N = Integer.parseInt(str.nextToken());
int K = Integer.parseInt(str.nextToken());
Position[] loc = new Position[K];
for (int i = 0; i < K; i++) {
loc[i] = new Position(Integer.parseInt(str.nextToken()) - 1,
Integer.parseInt(str.nextToken()) - 1);
}
int x = 0, y = 0;
int possibles = 0;
boolean ok;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
ok = true;
for (int k = 0; k < K; k++) {
x = loc[k].x;
y = loc[k].y;
if (i != x && j != y && Math.abs(i-x) !=
Math.abs(j-y)) {
ok = false;
break;
}
}
if (ok) possibles++;
}
}
out.println(possibles);
out.close();
}
}

class Position {
public int x;
public int y;
public Position() { x = y = 0; }
public Position(int ax, int ay) { x = ax; y = ay; }
}
```

## China's Mengyu Zhou wrote an extremely compact C solution

```#include <cstdio>

int n, m, x, y, h, v, l, r, s, ans;

int main() {
freopen ("paint2.in","r",stdin);
freopen("paint2.out","w",stdout);
scanf ("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
scanf ("%d%d", &x, &y);
x--; y--;
h[x]++; v[y]++;
l[y-x+n-1]++;
r[x+y]++;
s[x][y]++;
}
for (x = 0; x < n; x++)
for (y = 0; y < n; y++)
if (h[x] + v[y] + l[y-x+n-1] + r[x+y] - 3*s[x][y] == m)
ans++;
printf ("%d\n", ans);
return 0;
}
```

## Egypt's Mohamed Abd El-Wahab adds this

```#include <iostream>
using namespace std;

int ncow,row,col,d1,d2,n,k,coun;
int main() {
freopen("paint2.in","rt",stdin);
freopen("paint2.out","wt",stdout);
cin >>n>> k;
for(int i=0; i<k; i++) {
int r, c;
cin >> r >> c;
if(ncow[--r][--c])
continue;
coun++;
ncow[r][c]++;
col[c]++;
row[r]++;
d1[r+c]++;
d2[r-c+100]++;
}
int res=0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
if (row[i]+col[j]+d1[i+j]+d2[i-j+100]-3*ncow[i][j]==coun)
res++;
cout << res<< endl;
return 0;
}```