考虑以(x,y)为直角的等腰三角形个数F(x,y)，设绕(x,y)逆时针方向的第一个点是(a,b)，则另一个点坐标为(x+y-b,y-x+a)
需满足
0<=a<=X
0<=b<=Y
0<=x+y-b<=X
0<=y-x+a<=Y
(a,b)!=(x,y)
此时，F(x,y)=[min{x-y+Y,X}-max{x-y,0}+1]*[min{x+y,Y}-max{x+y-X,0}+1]-1
枚举x,y的值，就得到一个O(n2)的算法，可以AC前面一道了
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main(void)
{
int u,X,Y,x,y,t1,t2;
long long res;
scanf("%d",&u);
while(u--)
{
scanf("%d%d",&X,&Y);
res=0;
for(x=0;x<=X;x++)
for(y=0;y<=Y;y++)
{
t1=min(x-y+Y,X)-max(x-y,0)+1;
t2=min(x+y,Y)-max(x+y-X,0)+1;
res+=t1*t2-1;
}
printf("%lld\n",res);
}
return 0;
}
但是这样做后面那道题还是会超时，我们需要对公式进行转化，使它能够批量的求出
SF(x,y)的值
未完，待续……
posted on 2010-10-02 00:50
zxb 阅读(160)
评论(0) 编辑 收藏 引用