南阳题目206-矩形的个数

矫情吗；* 2022-07-28 05:04 178阅读 0赞

## 矩形的个数 ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 1

描述

在一个3\*2的矩形中，可以找到6个1\*1的矩形，4个2\*1的矩形3个1\*2的矩形，2个2\*2的矩形，2个3\*1的矩形和1个3\*2的矩形，总共18个矩形。  
  
给出A，B,计算可以从中找到多少个矩形。

输入

本题有多组输入数据（<10000），你必须处理到EOF为止  
  
输入2个整数A,B(1<=A,B<=1000)

输出

输出找到的矩形数。

样例输入

1 2
    3 2

样例输出

3
    18

来源

这个题要找到计算的公式就可以了，看了好多博客都是直接给的公式，这里我来详细解释一下

m\*n

取矩形的一个顶点在A（取每格的字母代表此格的左上角定点），则其要构成的矩形对角的另一个定点必须在除了A所在行和所在列的其他任意顶点 一共有（n）个

取矩形的一个顶点在A（取每格的字母代表此格的左上角定点），则其要构成的矩形对角的另一个定点必须在除了A所在行和所在列的其他任意顶点 一共有（n-1）个

一直取到第一行的最后一个格子的左上角一共有（1+2+3+。。。n）个矩形

然后重复第二行的B，C，D，E一直到m都和第一行的情况相同，共有（1+2+3+......m）

所以总共的个数就是（1+2+3+4+。。。+m）\*（1+2+3+4+。。。n）

得出公式 总个数为m\*n\*(m+1)\*(n+1)/4

但是注意数据很大，要用long long型（\_\_int64不支持，wa了一遍）

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int main()
    {
    	long long a,b,c,d,m,n,i;
    	while(scanf("%lld%lld",&m,&n)!=EOF)
    	{
    		printf("%lld\n",m*n*(m+1)*(n+1)/4);
    	}
    	return 0;
    }