这道题和黑书上在线段树那一部分举的火星地图的例子差不多，不过这题数据量很小，不用线段树做。
首先离散化，我觉得自已离散化的方法很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
古月残辉 阅读(930)
评论(0) 编辑 收藏 引用 所属分类:
计算几何