题目链接:codevs3044-矩形面积并
题意:
二维坐标,给n个矩阵,求面积。
题解:
线段树+扫描线。
扫描线的方向可以任定,我选的方向是从下到上,所以对于每个矩形,只需要考虑它的上下两边,即(L,R,U,F),LR表示边的顶点的横坐标,U表示纵坐标,F为标记,表示该边是矩形的顶边还是底边。
然后从较小的纵坐标开始枚举边,若当前边为底边,则在线段树上对这个区域进行标记,若遇到顶边,则取消标记。每扫描到一条边时,通过线段树快速计算此时覆盖在x轴上的总长度为L,并计算与下一条边的距离为S,当前的答案为ans+=L*S。
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 209;
int n;
struct node
{
double x1, x2, y;
int f;
} a[MAXN << 2];
double has[MAXN << 2], sum[MAXN << 2];
int lazy[MAXN << 2];
bool cmp(node x, node y)
{
return x.y < y.y;
}
int getid(double x)
{
int l = 1, r = 2 * n + 1;
while (l < r)
{
int mid = (l + r) / 2;
if (has[mid] < x)
l = mid + 1;
else if (has[mid] == x)
return mid;
else
r = mid;
}
}
void pushup(int l, int r, int rt)
{
if (lazy[rt])
sum[rt] = has[r + 1] - has[l];
else if (l == r)
sum[rt] = 0;
else
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void update(int L, int R, int val, int l, int r, int rt)
{
if (L <= l && r <= R)
{
lazy[rt] += val;
pushup(l, r, rt);
return;
}
int mid = (l + r) / 2;
if (L <= mid)
update(L, R, val, l, mid, rt << 1);
if (R > mid)
update(L, R, val, mid + 1, r, rt << 1 | 1);
pushup(l, r, rt);
}
int main()
{
while (scanf("%d", &n) && n)
{
memset(sum, 0, sizeof(sum));
memset(lazy, 0, sizeof(lazy));
for (int i = 1; i <= n; i++)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
a[i * 2 - 1].x1 = a[i * 2].x1 = x1;
a[i * 2 - 1].x2 = a[i * 2].x2 = x2;
a[i * 2 - 1].y = y1, a[i * 2 - 1].f = 1;
a[i * 2].y = y2, a[i * 2].f = -1;
has[i * 2 - 1] = x1, has[i * 2] = x2;
}
sort(has + 1, has + n * 2 + 1);
sort(a + 1, a + n * 2 + 1, cmp);
double ans = 0;
for (int i = 1; i <= n * 2; i++)
{
int l = getid(a[i].x1), r = getid(a[i].x2) - 1;
if (l <= r)
update(l, r, a[i].f, 1, 2 * n, 1);
ans += sum[1] * (a[i + 1].y - a[i].y);
}
printf("%.2f\n", ans);
}
return 0;
}