求 n (1 <= n <= 100)
个矩形的面积并。 题目链接：
http://poj.org/problem?id=1151
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 210;
const double eps = 1e-9;
struct line_t
{
double l_x, r_x, y;
bool flag;
};
bool cmp(const line_t &a, const line_t &b)
{
return a.y < b.y;
}
bool is_equal(const double &a, const double &b)
{
return abs(a - b) < eps;
}
int n;
double x[maxn];
int cnt_x, cnt_line;
line_t line[maxn];
int main()
{
int num = 0;
while(scanf("%d", &n) != EOF && n)
{
cnt_x = 0;
cnt_line = 0;
for(int i = 0; i < n; ++i)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
x[cnt_x++] = x1;
x[cnt_x++] = x2;
line[cnt_line].flag = false;
line[cnt_line].l_x = x1;
line[cnt_line].r_x = x2;
line[cnt_line++].y = y1;
line[cnt_line].flag = true;
line[cnt_line].l_x = x1;
line[cnt_line].r_x = x2;
line[cnt_line++].y = y2;
}
sort(line,line + cnt_line, cmp);
sort(x, x + cnt_x);
cnt_x = unique(x, x + cnt_x, is_equal) - x;
double area = 0.0;
for(int i = 0; i < cnt_x - 1; ++i)
{
int cnt = 0;
double now_y;
for(int j = 0; j < cnt_line; ++j)
if(line[j].l_x <= x[i] && line[j].r_x >= x[i + 1])
{
if(cnt == 0) now_y = line[j].y;
if(!line[j].flag) ++cnt;
else --cnt;
if(cnt == 0) area += (x[i + 1] - x[i]) * (line[j].y - now_y);
}
}
printf("Test case #%d\n", ++num);
printf("Total explored area: %.2lf\n\n", area);
}
return 0;
}
posted on 2011-10-08 10:59
wuxu 阅读(231)
评论(0) 编辑 收藏 引用 所属分类:
计算几何