这题和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 == -1) break;
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 == 0) break;
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) 编辑 收藏 引用 所属分类:
计算几何