Cerința

Pe o tablă de șah de dimensiune n se află m regine. O regină atacă o altă regină dacă cele două se află pe aceeași linie, coloană sau diagonală și între ele nu se află alte regine. Determinați numărul maxim p de regine care sunt atacate de o aceeași regină și numărul q de regine care atacă p alte regine.

Date de intrare

Fișierul de intrare regine.in conține pe prima linie numerele n m; următoarele m linii conțin perechi i j reprezentând linia și coloana unde se află poziționată o regină.

Date de ieșire

Fișierul de ieșire regine.out va conține pe prima linie numerele p q, separate prin exact un spațiu, reprezentând valorile de mai sus.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 500
• 1 ≤ i,j ≤ n
• pe tablă nu există două regine suprapuse

Exemplu

regine.in

8 9
1 7
2 2 
2 8
4 1
5 2
5 5
5 8
7 2
7 7

regine.out

5 1

Explicație

#include <bits/stdc++.h>
using namespace std;
ifstream cin("regine.in");
ofstream cout("regine.out");
const int di[]={-1,-1,-1, 0, 0, 1, 1, 1};
const int dj[]={-1, 0, 1,-1, 1,-1, 0, 1};

int a[105][105], n, m , i , j , p , q;
int main()
{
    cin  >> n >> m ;
    for(int k = 1 ; k <= m ; ++k)
    {
        cin >> i >> j;
        a[i][j] = 1;
    }
    
    for(int i =1 ; i <= n ; ++i)
        for(int j =1 ; j <= n ; ++j)
            if(a[i][j] == 1)
            {
                int cnt = 0;
                for(int k = 0 ; k < 8 ; k ++)
                {
                    int x = 1;
                    while(i + di[k] * x > 0 && i + di[k] * x <= n && j + dj[k] * x > 0 && j + dj[k] * x <= n && a[i + di[k] * x][j + dj[k] * x] == 0)
                        x ++;
                    if(a[i + di[k] * x][j + dj[k] * x] == 1)  
                        cnt ++;
                }
                if(cnt > p) 
                    p = cnt, q = 1;
                else if(cnt == p) 
                    q ++;
            }
    
    cout << p << " " << q << endl;
    return 0;
}