考古学家在神秘岛上发现了一处古代先民的遗迹。该遗迹的地面建筑已经倒塌，只留下地基。经初步考证得知该遗迹外围呈矩形，内部由东西走向和南北走向的石头墙隔成一个个大小不一的矩形房间，（如图1所示）。该遗迹的来历是一个谜，考古学家试图通过计算其中房间的数量来得到线索。但该遗迹的结构十分复杂，直接计算容易出错。于是，他们决定利用计算机进行计算。为此，他们测量出了该遗迹的长和宽，以及其内部每堵墙两端的位置。测量时参考坐标系按如下方法设定：原点取在遗迹西南角的位置上（图1 中的位置o），x轴的方向由西指向东，y轴的方向由南指向北。在测量中，首尾相接的同一走向的墙当作一堵墙处理。他们发现测量得到的所有数据都是非负整数。现在请你设计一个程序求该遗迹中的房间数量。



图1




Input

输入的第一行含一个正整数k，表示测试例个数。下面紧接着k个测试例的数据。每个测试例数据的第一行含四个正整数a，b，m和n（m，n<=1000），其中，a和b分别表示遗迹外围东西向和南北向的长度；m和n分别表示遗迹内部东西走向和南北走向的墙的数目。接下来的m行每行含3个非负整数x1, x2和y，表示一堵东西走向的墙的两端位置，其中（x1, y）和（x2, y）分别为墙的西端和东端的位置坐标。再接下来的n行每行同样含3个非负整数x, y1和y2，表示一堵南北走向的墙的两端位置，其中（x, y1）和（x, y2）分别为墙的南端和北端的位置坐标。同一行的数据之间用一个空格隔开，两个测试例之间用一个空行隔开。

Output

对应每个测试例输出一个整数，表示遗迹中房间的数量。一个整数占一行。

Sample Input


2
4 4 1 1
0 4 2
2 0 4

3 6 2 1
0 1 4
1 3 2
1 0 6

Sample Output


4
4

Source

[[it] 本帖最后由 心剑菩提 于 2008-3-11 20:40 编辑 [/it]]

各位大哥大姐 有什么心得想法啊 交流一下

#include <stdio.h>
int main ()
{
   int t;
    scanf("%d",&t);
     while(t--)
    {
      int a,b,m,n;
      scanf("%d%d%d%d",&a,&b,&m,&n);
      int x1[m+2],x2[m+2],y[m+2],y1[n+2],y2[n+2],x[n+2],i,j;
      for(i=1;i<=m;i++)
        scanf("%d%d%d",&x1[i],&x2[i],&y[i]);
      for(i=1;i<=n;i++)
        scanf("%d%d%d",&x[i],&y1[i],&y2[i]);
      x1[0]=0;x2[0]=a;y[0]=0;
      x1[m+1]=0;x2[m+1]=a;y[m+1]=b;
      y1[0]=0;y2[0]=b;x[0]=0;
      y1[n+1]=0;y2[n+1]=b;x[n+1]=a;
      int num=0;
      for(i=0;i<m+1;i++)
      {
        for(j=0;j<n+2;j++)
        {
          if((x[j]==x1[i])+(x[j]==x2[i])+((x[j]>x1[i])&&(x2[i]>x[j])))
              if ((y2[j]>y[i])&&(y1[j]<=y[i]))
                  num++;
        }
        num--;
      }
      printf("%d\n",num);    
    }
    return 0;
}

没有图看不明白

你的图呢 我想做做````