随笔-20  评论-16  文章-36  trackbacks-0
      这题和PKU 1151几乎是一样的,只是数据量和类型有些差别,之所以再贴这题,是因为学习了下Felicia大牛的代码,果然比我的简单很多很多……
      下面解释下代码的意思,大体思路和我是一样的,只是实现的时候很巧妙,首先,他把一个矩形分成两部分记录,以y坐标作为关键字,用flag表示是上面的还是下面的y坐标,这样,他排序只进行了两次,一次对所有的矩形信息排序,一次对所有的x区间排序,由于计算的时候其实是和x坐标的顺序没有关系的,我自已写的那个程序排序等于是浪费了……他的去重也很强悍,调用unique()函数去重,返回末尾元素的指针,再减去数组首指针,得到数组的大小~~最后求每一段的面积的时候,他又用了点小技巧,由于矩形信息是按y坐标排好序的,因此如果当前进来的坐标是flag=0的坐标的话,说明它比当前最小的y坐标要大,把这个矩形加到当前的“队列”中来,cnt++,如果当前进来的坐标是flag=1的坐标的话,说明有一个矩形已经结束了,cnt--,当cnt减到0且进来的是flag=0的坐标的话,说明当前最小的y坐标也比这个矩形最大的y坐标要大,故重新建立“队列”,并更新area值。
      下面是他的代码,有改动。
#include <iostream>
#include 
<cmath>
#include 
<algorithm>
using namespace std;
const int maxn = 4010;

typedef 
struct line_t{
    
int l, r, y;
    
int flag;
}
;

bool operator <(const line_t &a, const line_t &b){
    
return a.y < b.y;
}


bool d_equal(const int &a, const int &b){
    
return abs(a - b) < 1e-9;
}


int n;
int x[maxn];
int cnt_x, cnt_line;
line_t line[maxn];

int main(){
    
while (1){
        cnt_x 
= 0;
        cnt_line 
= 0;
        
while (1){
            
int x1, y1, x2, y2;
            scanf(
"%d%d%d%d"&x1, &y1, &x2, &y2);
            
if (x1 == -1break;
            x[cnt_x
++= x1;
            x[cnt_x
++= x2;
            line[cnt_line].flag 
= 0;
            line[cnt_line].l 
= x1;
            line[cnt_line].r 
= x2;
            line[cnt_line
++].y = y1;
            line[cnt_line].flag 
= 1;
            line[cnt_line].l 
= x1;
            line[cnt_line].r 
= x2;
            line[cnt_line
++].y = y2;
        }

        sort(line, line 
+ cnt_line);
        sort(x, x 
+ cnt_x);
        cnt_x 
= unique(x, x + cnt_x, d_equal) - x;
        
if (cnt_x == 0break;
        
int area = 0;
        
for (int i = 0; i < cnt_x - 1; i++){
            
int cnt = 0;
            
int now_y;
            
for (int j = 0; j < cnt_line; j++if (line[j].l <= x[i] && line[j].r >= x[i + 1]){
                
if (cnt == 0) now_y = line[j].y;
                
if (line[j].flag == 0) cnt++;
                
else cnt--;
                
if (cnt == 0) area += (x[i + 1- x[i]) * (line[j].y - now_y);
            }

        }

        printf(
"%d\n", area);
    }

    
return 0;
}
posted on 2009-06-27 17:24 古月残辉 阅读(673) 评论(0)  编辑 收藏 引用 所属分类: 计算几何

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