Cod sursa(job #2341102)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 11 februarie 2019 15:49:10
Problema Dreptunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin  ("dreptunghiuri.in");
ofstream fout ("dreptunghiuri.out");

typedef long long ll;
const int Nmax = 405;

int N, M, i, j, k;
ll ans;
vector< pair<int, int> > where[Nmax*Nmax*2];

int min4(int x, int y, int z, int t)
{
    return min(min(x, y), min(z, t));
}
int max4(int x, int y, int z, int t)
{
    return max(max(x, y), max(z, t));
}

int get_answer(pair<int,int> A, pair<int,int> B)
{
    int X1, X2, Y1, Y2;
    X1 = A.first; Y1 = A.second;
    X2 = B.first; Y2 = B.second;

    if((X1 - X2) % 2 != 0) return 0;
    if((Y2 - Y1) % 2 != 0) return 0;

    int l1, l2, l3, c1, c2, c3, lmin, lmax, cmin, cmax;

    l1 = (X1 - X2) / 2;
    l2 = (X1 + X2) / 2;
    l3 = X1;
    c1 = (Y1 - Y2) / 2;
    c2 = (Y1 + Y2) / 2;
    c3 = Y1;

    lmin = min4(0, l1, l2, l3);
    lmax = max4(0, l1, l2, l3);
    cmin = min4(0, c1, c2, c3);
    cmax = max4(0, c1, c2, c3);

    if(-lmin > N - lmax) return 0;
    if(-cmin > M - cmax) return 0;
    return (N - lmax + lmin + 1) * (M - cmax + cmin + 1);
}

int main()
{
    fin >> N >> M; --N; --M;

    for(i=0; i<=N; ++i)
        for(j=0; j<=M; ++j)
        {
            where[i*i + j*j].push_back({i, j});
            if(i && j) where[i*i + j*j].push_back({i, -j});
        }

    for(i=1; i<=N*N + M*M; ++i)
        for(j=0; j<where[i].size(); ++j)
            for(k=0; k<j; ++k)
                ans += get_answer(where[i][j], where[i][k]);

    fout << ans << '\n';
    return 0;
}