首页 > ACM题库 > HDU-杭电 > HDU 1255 覆盖的面积-线段树-[解题报告] C++
2013
12-04

HDU 1255 覆盖的面积-线段树-[解题报告] C++

覆盖的面积

问题描述 :

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

输入:

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.

注意:本题的输入数据较多,推荐使用scanf读入数据.

输出:

对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.

样例输入:

2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1

样例输出:

7.63
0.00

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

这题…如果会求面积并的话,面积交就不是问题了。只需要将原先判断线段树中cover值为大于等于1改为大于等于2即可!

什么都不会的同学,请看上一个随笔http://www.cnblogs.com/ka200812/archive/2011/11/13/2247064.html

 

#include<iostream>
 #include<string>
 #include<stdlib.h>
 using namespace std;
 
 typedef struct
 {
     double x;
     double y_up;
     double y_down;
     int l_r;
 }LINE;
 
 typedef struct
 {
     double x;
     double y_up;
     double y_down;
     int cover;
     bool has_child;
 }TREE;
 
 int cmp(const void *a,const void *b)
 {
     return *(double *)a>*(double *)b? 1: -1;
 }
 
 TREE tree[1000*1001];
 LINE line[2002];
 int n,index;
 double x1,y1,x2,y2;
 double y[2002];
 
 void build(int i,int l,int r)
 {
     tree[i].cover=0;
     tree[i].x=-1;
     tree[i].has_child=true;
     tree[i].y_up=y[r];
     tree[i].y_down=y[l];
     if(l+1==r)
     {
         tree[i].has_child=false;
         return;
     }
     int mid=(l+r)>>1;
     build(2*i,l,mid);
     build(2*i+1,mid,r);
 }
 
 double insert(int i,double l,double r,double x,int l_r)
 {
     if(tree[i].y_up<=l || tree[i].y_down>=r)
         return 0;
     if(!tree[i].has_child)
     {
         if(tree[i].cover>1)
         {
             double ans=(x-tree[i].x)*(tree[i].y_up-tree[i].y_down);
             tree[i].x=x;
             tree[i].cover+=l_r;
             return ans;
         }
         else
         {
             tree[i].cover+=l_r;
             tree[i].x=x;
             return 0;
         }
     }
     else
         return insert(2*i,l,r,x,l_r)+insert(2*i+1,l,r,x,l_r);
 }
 
 int main()
 {
     int t,i;
     //freopen("D:\\in.txt","r",stdin);
     cin>>t;
     while(t--)
     {
         cin>>n;
         index=1;
         for(i=1;i<=n;i++)
         {
             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 
             line[index].x=x1;
             line[index].l_r=1;
             line[index].y_up=y2;
             line[index].y_down=y1;
             y[index]=y1;
             index++;
 
             line[index].x=x2;
             line[index].l_r=-1;
             line[index].y_up=y2;
             line[index].y_down=y1;
             y[index]=y2;
             index++;
         }
         qsort(y+1,2*n,sizeof(y[0]),cmp);
         qsort(line+1,2*n,sizeof(line[0]),cmp);
         build(1,1,index-1);
         double ans=0;
         for(i=1;i<index;i++)
         {
             ans+=insert(1,line[i].y_down,line[i].y_up,line[i].x,line[i].l_r);
         }
         printf("%.2lf\n",ans);
     }
     return 0;
 }


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。