首页 > ACM题库 > HDU-杭电 > hdu 2524 矩形A + B-计算几何-[解题报告]C++
2014
02-09

hdu 2524 矩形A + B-计算几何-[解题报告]C++

矩形A + B

问题描述 :

给你一个高为n ,宽为m列的网格,计算出这个网格中有多少个矩形,下图为高为2,宽为4的网格.

输入:

第一行输入一个t, 表示有t组数据,然后每行输入n,m,分别表示网格的高和宽 ( n < 100 , m < 100).

输出:

第一行输入一个t, 表示有t组数据,然后每行输入n,m,分别表示网格的高和宽 ( n < 100 , m < 100).

样例输入:

2
1 2
2 4

样例输出:

3
30

http://acm.hdu.edu.cn/showproblem.php?pid=2524

题目分析:

方法一:

  根据题目中所给出的图,将图的左上角点看为(0,0),那么其它交点也有了坐标,我们需要做的是让坐标相见均不为零即可,但需要注意的是不能重复计算已经记录过的矩形。

例如图中有(0,0),(2,2)两个坐标,前者减后者与后者减前者均不为零,但是表达的却是同一个矩形,因此需要特别注意。

方法二:

  将每一行有多少个矩形与每一列有多少个矩形计算出来,其任意的行矩形与列矩形组合均为一种矩形(即二者相乘为所要求得结果)。那么问题落在了求某一行或某一列的问题上,现假设有一个n=1,m=3的矩形,当m为1的时候有1个矩形,当m为2的时候有2个矩形,当m为3的时候有3个矩形(其中的不包括前者已经算过的,例如,若m=2的时候本应有3个矩形,但是由于在m=1的时候已经把m=2中的一种情况涵盖了,因此去掉重复的情况),因此总矩形数为1+2+3,可求得公式为(1+m)*m/2,同理也可以求出行矩形。

附源码如下:

方法一:

#include <stdio.h>
 
 int main()
 {
     int n,m;
     int testNum;
     int count;
     scanf("%d",&testNum);
 
     while(testNum--)
     {
         count=0;
         scanf("%d %d",&n,&m);
         for(int i=0;i<n;i++)
         {
             for(int j=0;j<m;j++)
             {
                 for(int k=i+1;k<=n;k++)
                 {
                     for(int l=j+1;l<=m;l++)
                     {
                         if(k-i!=0&&l-j!=0)
                             count++;
                     }
                 }
             }
         }
         //
         printf("%d\n",count);
     }
 
 
 
     return 0;
 }

方法二:

#include <stdio.h>
 
 int main()
 {
     int n,m;
     int testNum;
     int count;
     scanf("%d",&testNum);
 
     while(testNum--)
     {
         count=0;
         scanf("%d %d",&n,&m);
         count=( (1+n)*n/2 ) * ( (1+m)*m/2 );
         //
         printf("%d\n",count);
     }
 
 
 
     return 0;
 }

 

解题转自:http://www.cnblogs.com/heweiyou/archive/2013/04/04/2999851.html


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.