扫描线用于求解n个图形的面积的并,主要思想就是用一条线从左到右（或者从上到下）扫描整个所有图形，其实方向无所谓的。这里以一个题为例讲解亚特兰蒂斯
有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。
其中一些甚至包括岛屿部分地图。
但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。
您的朋友Bill必须知道地图的总面积。
你自告奋勇写了一个计算这个总面积的程序。
输入格式
输入包含多组测试用例。
对于每组测试用例，第一行包含整数n，表示总的地图数量。
接下来n行，描绘了每张地图，每行包含四个数字
当输入用例n=0时，表示输入终止，该用例无需处理。
输出格式
每组测试用例输出两行。
第一行输出”Test case #k”，其中k是测试用例的编号，从1开始。
第二行输出“Total explored area：a”，其中a是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。
在每个测试用例后输出一个空行。
数据范围
输入样例：
2
10 10 20 20
15 15 25 25.5
0
输出样例：
Test case #1
Total explored area: 180.00
对于这道题我们可以从左到右扫描所有图形，那么我们就以对x排序，从小到大扫描，由于y比较大，所以需要离散化，对于每一条直线我们需要更新它对整个区间覆盖的范围进行更新，假如它的范围是[L,R],那么其实我们更新的是[L,R),因为对于每一个小区间，我们只跟新它的左部分，所以是开区间，同时这也为后面计算总长len提供了方便。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 * 1000 + 10;
double ans = 0;
int n, c[220],id[maxn];
double a[220];
struct node { double x, y1, y2;int k,id; }p[220];
bool cmp(node a, node b) {
return a.x < b.x;
}
int cnt = 1,num=1;
void add(double x1, double y1, double x2, double y2) {
p[cnt].x = x1, p[cnt].y1 = y1, p[cnt].y2 = y2, p[cnt].k = 1,p[cnt].id=cnt++;
p[cnt].x = x2, p[cnt].y1 = y1, p[cnt].y2 = y2, p[cnt].k = -1, p[cnt].id = cnt++;
}
int getid(double v) { //获取v离散化后的值
return lower_bound(a+1,a+num,v)-a;
}
int main() {
int kase = 1;
while (cin >> n && n) {
ans = 0; num = 1; cnt = 1;
double x1, y1, x2, y2;
for (int i = 1; i <= n; i++) {
cin >> x1 >> y1 >> x2 >> y2;
add(x1, y1, x2, y2);
a[num++] = y1;
a[num++] = y2;
}
sort(a + 1, a + num);
num = unique(a + 1, a +num) - a; //对y进行排序去重，离散化
sort(p + 1, p + cnt, cmp);
memset(c, 0, sizeof(c));
for (int i = 1; i < 2 * n; i++) {
int k = p[i].k;
int L = getid(p[i].y1), R = getid(p[i].y2); //获取区间的左右值
for (int j = L; j < R; j++)c[j] += k; //整理不能更新到R，切记
double len = 0;
for (int j = 1; j < 2 * n; j++)if (c[j])len += (a[j + 1] - a[j]);
ans += (p[i + 1].x - p[i].x)*len;
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",kase++,ans);
}
return 0;
}
另一种离散化的方法：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 * 1000 + 10;
double ans = 0;
int n, c[220],id[220][3];
double a[220];
struct node { double x; int id, k; }p[220],q[220];
bool cmp(node a, node b) {
return a.x < b.x;
}
int cnt = 1,num=1;
int getid(double v) {
return lower_bound(a+1,a+num,v)-a;
}
int main() {
int kase = 1;
while (cin >> n && n) {
ans = 0;
double x1, y1, x2, y2;
for (int i = 1; i <= n; i++) {
cin >> x1 >> y1 >> x2 >> y2;
p[i * 2 - 1].x = x1, p[i * 2 - 1].id = i, p[i * 2 - 1].k = 1;
p[i * 2].x = x2, p[i * 2].id = i, p[i * 2 ].k = -1;
q[i * 2 - 1].x = y1, q[i * 2 - 1].id = i, q[i * 2 - 1].k = 0;
q[i * 2 ].x = y2, q[i * 2 ].id = i, q[i * 2].k = 1;
}
sort(p + 1, p + n*2+1,cmp);
sort(q+1,q+1+2*n,cmp);
memset(id,0,sizeof(id));
for (int i = 1; i <= n*2; i++)id[q[i].id][q[i].k] = i;
memset(c,0,sizeof(c));
for (int i = 1; i < 2 * n; i++) {
int k = p[i].k; int kid = p[i].id;
int L = id[kid][0], R = id[kid][1];
for (int j = L; j < R; j++)c[j] += k;
double len = 0;
for (int j = 1; j < 2 * n; j++)if (c[j])len += (q[j + 1].x - q[j].x);
ans += (p[i + 1].x - p[i].x)*len
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",kase++,ans);
}
return 0;
}
上述代码复杂度都是O(n^2)的，利用线段树维护c 数组，可以优化到O(nlogn)，对于每个节点我们维护两个值，cnt——这段区间被覆盖的次数，len——这段区间中被覆盖的长度，当我们更新一段区间的时，如果cnt！=0，那么tree[rt].len = a[tree[rt].R + 1] - a[tree[rt].L]，如果cnt==0并且当前节点已经是叶子节点，那么len=0，如果不是叶子节点，那么tree[rt << 1].len + tree[rt << 1 | 1].len; 具体参看代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 * 1000 + 10;
double ans = 0;
int n, c[220],id[maxn];
double a[220];
struct node { double x, y1, y2;int k,id; }p[220];
bool cmp(node a, node b) {
return a.x < b.x;
}
int cnt = 1,num=1;
void add(double x1, double y1, double x2, double y2) {
p[cnt].x = x1, p[cnt].y1 = y1, p[cnt].y2 = y2, p[cnt].k = 1,p[cnt].id=cnt++;
p[cnt].x = x2, p[cnt].y1 = y1, p[cnt].y2 = y2, p[cnt].k = -1, p[cnt].id = cnt++;
}
int getid(double v) {
return lower_bound(a+1,a+num,v)-a;
}
struct {
struct {
int L, R,cnt;
double len;
}tree[200*4];
void built(int rt,int L,int R) {
tree[rt].L = L; tree[rt].R = R;
tree[rt].cnt = 0; tree[rt].len = 0;
if (L == R)return;
int mid = (L + R) >> 1;
built(rt << 1, L, mid);
built(rt << 1|1, mid+1,R);
}
void down(int rt) {
if (tree[rt].cnt) tree[rt].len = a[tree[rt].R + 1] - a[tree[rt].L];
else if (tree[rt].L == tree[rt].R)tree[rt].len = 0;
else tree[rt].len = tree[rt << 1].len + tree[rt << 1 | 1].len;
}
void change(int rt,int L,int R,int k) {
if (tree[rt].L >= L && tree[rt].R <= R) {
tree[rt].cnt += k;
down(rt);
return;
}
int mid = (tree[rt].L + tree[rt].R) >> 1;
if (mid >= L)change(rt<<1,L,R,k);
if (mid + 1 <= R)change(rt<<1|1,L,R,k);
down(rt);
}
double query() { return tree[1].len; }
}T;
int main() {
int kase = 1;
while (cin >> n && n) {
ans = 0; num = 1; cnt = 1;
double x1, y1, x2, y2;
for (int i = 1; i <= n; i++) {
cin >> x1 >> y1 >> x2 >> y2;
add(x1, y1, x2, y2);
a[num++] = y1;
a[num++] = y2;
}
sort(a + 1, a + num);
num = unique(a + 1, a +num) - a;
sort(p + 1, p + cnt, cmp);
memset(c, 0, sizeof(c));
T.built(1,1,num-1);
for (int i = 1; i < 2 * n; i++) {
int k = p[i].k;
int L = getid(p[i].y1), R = getid(p[i].y2);
T.change(1,L,R-1,k);
ans += (p[i + 1].x - p[i].x)*T.query();
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",kase++,ans);
}
return 0;
}
京公网安备 11010502036488号