<—点个赞吧QwQ
宣传一下算法提高课整理
有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。
其中一些甚至包括岛屿部分地图。
但不幸的是,这些地图描述了亚特兰蒂斯的不同区域。
您的朋友 Bill 必须知道地图的总面积。
你自告奋勇写了一个计算这个总面积的程序。
输入格式
输入包含多组测试用例。
对于每组测试用例,第一行包含整数 $n$,表示总的地图数量。
接下来 $n$ 行,描绘了每张地图,每行包含四个数字 $x_1,y_1,x_2,y_2$(不一定是整数),$(x_1,y_1)$ 和 $(x_2,y_2)$ 分别是地图的左上角位置和右下角位置。
注意,坐标轴 $x$ 轴从上向下延伸,$y$ 轴从左向右延伸。
当输入用例 $n=0$ 时,表示输入终止,该用例无需处理。
输出格式
每组测试用例输出两行。
第一行输出 Test case #k
,其中 $k$ 是测试用例的编号,从 $1$ 开始。
第二行输出 Total explored area: a
,其中 $a$ 是总地图面积(即此测试用例中所有矩形的面积并,注意如果一片区域被多个地图包含,则在计算总面积时只计算一次),精确到小数点后两位数。
在每个测试用例后输出一个空行。
数据范围
$1 \\le n \\le 10000$,
$0 \\le x_1 < x_2 \\le 100000$,
$0 \\le y_1 < y_2 \\le 100000$
注意,本题 $n$ 的范围上限加强至 $10000$。
输入样例:
2
10 10 20 20
15 15 25 25
0
输出样例:
Test
Total explored area: 180.00
样例解释
样例所示地图覆盖区域如下图所示,两个矩形区域所覆盖的总面积,即为样例的解。
思路
没啥可说的,就是根据每一个 $y$,求横着覆盖的 $x$ 轴上的长度乘上 $\text{d}y$ 的和就好了。这里也是网上大部分题解停止的地方。
重点讲一下线段树的细节。
首先,可以用懒标记实现,但是这里可以不用。因为覆盖一个完整区间的时候,我们只需要关心比它更大的就好了,更小,查询时不会涉及到。
一两句话讲不太清楚,感性理解一下,其实还是能懂的。
当然实在不懂可以写懒标记。
代码
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};
bool LAST = false;
istream& operator >> (istream& in,char* s) {
if (LAST) return in;
char ch = cin.get ();
while ((isspace (ch) || ch == '\n') && ch != EOF) ch = cin.get ();
int n = 0;
while (!(isspace (ch) || ch == '\n') && ch != EOF) s[n++] = ch,ch = cin.get ();
s[n] = '\0';
if (ch == EOF) LAST = true;
return in;
}
const int N = 100010;
int n,m;
struct scan_line {
double x1,x2,y;
int mark;
}line[2 * N];
double all[2 * N];
struct segment_tree_node {
int l,r,cnt;
double len;
}tr[16 * N];
void push_up (int u) {
if (tr[u].cnt) tr[u].len = all[tr[u].r + 1] - all[tr[u].l];
else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}
void build (int u,int l,int r) {
tr[u] = {l,r,0,0};
if (l == r) return ;
int mid = l + r >> 1;
build (u << 1,l,mid),build (u << 1 | 1,mid + 1,r);
}
void modify (int u,double l,double r,int c) {
if (all[tr[u].r + 1] <= l || r <= all[tr[u].l]) return ;
if (l <= all[tr[u].l] && all[tr[u].r + 1] <= r) {
tr[u].cnt += c;
push_up (u);
return ;
}
int mid = tr[u].l + tr[u].r >> 1;
modify (u << 1,l,r,c),modify (u << 1 | 1,l,r,c);
push_up (u);
}
int main () {
int T = 1;
while (cin >> n,n) {
for (int i = 1;i <= n;i++) {
double x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
line[i * 2 - 1] = {x1,x2,y1,1},line[i * 2] = {x1,x2,y2,-1};
all[i * 2 - 1] = x1,all[i * 2] = x2;
}
n <<= 1;
sort (all + 1,all + n + 1);
sort (line + 1,line + n + 1,[](scan_line x,scan_line y) {
return x.y < y.y;
});
m = unique (all + 1,all + n + 1) - all - 1;
build (1,1,m - 1);
double ans = 0;
for (int i = 1;i < n;i++) {
modify (1,line[i].x1,line[i].x2,line[i].mark);
ans += (double)tr[1].len * (line[i + 1].y - line[i].y);
}
cout << "Test case #" << T++ << endl;
cout << "Total explored area: " << fixed << setprecision (2) << ans << endl << endl;
}
return 0;
}
今天学校有一题就是扫描线板题........
Orz
Orz 大佬手刃扫描线
抄的