Cod sursa(job #350670)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 25 septembrie 2009 11:54:55
Problema Dreptunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define pb push_back
#define size(V) ((int)(V.size()))
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair
#define mod 654321
#define oo 1<<30

#define IN  "dreptunghiuri.in"
#define OUT "dreptunghiuri.out"

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;
template<class T> string toString(T n) {ostringstream ost;ost<<n;ost.flush();return ost.str();}
typedef vector<string> VS;

int N,M;
bool Sqrt[1<<20];

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d%d",&N,&M);
}

II int compute(int W,int H)
{
	int count = (N - W + 1) * (M - H + 1);
	int P,rez = 0;
	
	--H;
	FOR(i,2,W-1)
		if(H * H >= 4 * (P = (i - 1) * (W - i) ) && Sqrt[H * H - P * 4] )
			if(H * H == P * 4)
				++rez;
			else
				rez += 2;
//	printf("pt %d cu %d %d nr=%d\n",x,y,rez / count,count);
	
	return rez * count;
}

II void solve()
{
	int rez = 0;
	
	FOR(i,0,1000) Sqrt[i * i] = true;
	rez += N * (N - 1) * M * (M - 1) >> 2;
	
	FOR(x,3,N)
	FOR(y,3,M)
		rez += compute(x,y);
	
	printf("%d\n",rez);
}

int main()
{
	scan();
	solve();
	return 0;
}