随笔-20  评论-16  文章-36  trackbacks-0
      这道题和黑书上在线段树那一部分举的火星地图的例子差不多,不过这题数据量很小,不用线段树做。
      首先离散化,我觉得自已离散化的方法很CUO,用了类似归并排序的方法把所有的x坐标去重排序后放在corx[]中,然后再对每一段计算面积,计算面积的时候我又对y坐标进行了一次排序,做的很繁,不知道大牛们是怎么离散化的,去学习学习~~
      先发下我的代码:
#include <iostream>
#include 
<algorithm>
using namespace std;

int n;
struct Rectangle{
    
double x1, y1, x2, y2;
}
rec[101];
bool cmp( Rectangle r1, Rectangle r2 ){
    
if( r1.x1< r2.x1 )    return true;
    
else if( r1.x1> r2.x1 )    return false;
    
if( r1.y1> r2.y1 )    return true;
    
else if( r2.y1< r2.y1 )    return false;
    
if( r1.x2< r2.x2 )    return true;
    
else if( r1.x2> r2.x2 )    return false;
    
if( r1.y2> r2.y2 )    return true;
    
return false;
}

struct Ycor{
    
double max, min;
}
ycor[101];
bool cmp2( Ycor y1, Ycor y2 ){
    
return y1.max>y2.max || (y1.max==y2.max&&y1.min<y2.min);
}

int main(){
    
int i, j, k, l, t= 1;
    
double corx[201], tmp[101], area, ymax, ymin;
    
while( scanf("%d",&n) && n ){
        area
= 0;
        
for( i= 0; i< n; i++ ){
            scanf(
"%lf%lf%lf%lf",&rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);
            tmp[i]
= rec[i].x2;
        }

        sort(rec,rec
+n,cmp);
        sort(tmp,tmp
+n);
        
for( i= 0, j= 0, k= 0; i< n && j< n; ){
            
if( rec[i].x1< tmp[j] ){
                
if( corx[k-1]!= rec[i].x1 )
                    corx[k
++]= rec[i].x1;
                i
++;
            }

            
else if( rec[i].x1> tmp[j] ){
                
if( corx[k-1]!=tmp[j] )
                    corx[k
++]= tmp[j];
                j
++;
            }

            
else{
                
if( corx[k-1]!=tmp[j] )
                    corx[k
++]= tmp[j];
                i
++, j++;
            }

        }

        
while( i< n )    corx[k++]= rec[i++].x1;
        
while( j< n )    corx[k++]= tmp[j++];
        
for( i= 1; i< k; i++ ){
            ycor[
0].max= ycor[0].min= 0;
            
for( j= 0, l= 0; j< n; j++ )
                
if( rec[j].x1<=corx[i-1&& rec[j].x2>=corx[i] )
                    ycor[l].max
= rec[j].y2, ycor[l++].min= rec[j].y1;
            sort(ycor,ycor
+l,cmp2);
            ymax
= ycor[0].max, ymin= ycor[0].min;
            
for( j= 1; j< l; j++ ){
                
if( ycor[j].max< ymin ){
                    area
+= (corx[i]-corx[i-1])*(ymax-ymin);
                    ymax
= ycor[j].max, ymin= ycor[j].min;
                }

                
else if( ycor[j].min< ymin )    ymin= ycor[j].min;
            }

            area
+= (corx[i]-corx[i-1])*(ymax-ymin);
        }

        printf(
"Test case #%d\nTotal explored area: %.2lf\n\n",t++,area);
    }

    
return 0;
}

posted on 2009-06-26 15:59 古月残辉 阅读(947) 评论(0)  编辑 收藏 引用 所属分类: 计算几何

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理