题目地址: http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3826
分两种情况计算。
第一种情况,两个圆水平相切、或者竖直相切。
这种情况很好计算,假设一个(以最大圆直径为宽、以两圆直径之和为长)矩形,在n*m的范围内有多少放法,计算出来即可。
第二种情况,两个圆沿斜线相切(斜线长度为任意 勾股数组 的斜边长度)。
这时候只要枚举斜线两端圆的半径(从1 到 len-1),分别求出所能容纳它的相应的矩形,然后求这个矩形在n*m的范围内有多少放法即可。
==================================================================================================================
PS: WA了一下午,刚开始是少算(只计算以勾股数组的两边为半径的圆)。。。
后来是多算(代表沿斜线相切的圆的矩形大小算搓了,比实际偏小,导致计算的时候有更多的放法)。。。
比赛结束后不久。。。才发现写漏了判断。。。囧。。。 改了就AC了。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int has[651000];
int x[10000],y[10000],z[10000],cnt;
void deal(){
int i,j,k;
cnt=0;
for(i=1;i<=800;i++)
has[i*i]=i;
for(i=1;i<500;i++)
for(j=i+1;j<500;j++){
k=j*j+i*i;
if(has[k]){
x[cnt]=i;
y[cnt]=j;
z[cnt]=has[k];
cnt++;
}
}
}
int main(){
int t,tt,n,m,i,j,mx,h,w,k1,k2;
long long sum,tmp;
deal();
scanf("%d",&t);
for(tt=1;tt<=t;tt++){
scanf("%d%d",&n,&m);
sum=0;
mx=max(n,m);
for(i=2;i<mx;i+=2){ // 第一种情况
for(j=i;i+j<=mx;j+=2){
h=i+j;
w=max(i,j);
tmp=0;
if(n>=h && m>=w)
tmp+=(n-h+1)*(m-w+1);
if(m>=h && n>=w)
tmp+=(m-h+1)*(n-w+1);
if(i!=j) tmp*=2;
sum+=tmp;
}
}
for(i=0;i<cnt;i++){ // 第二种情况
for(j=1;j<z[i];j++){
tmp=0;
h=max(z[i]+x[i],2*max(j,z[i]-j));
w=max(z[i]+y[i],2*max(j,z[i]-j));
if(n>=h && m>=w)
tmp+=(n-h+1)*(m-w+1);
if(m>=h && n>=w)
tmp+=(m-h+1)*(n-w+1);
sum+=tmp*2;
}
}
printf("Case %d: %lld\n",tt,sum);
}
return 0;
}