标签：std 数字 onclick 面积并 xpl pre ase ++ 固定
传送门
题目描述
有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。
其中一些甚至包括岛屿部分地图。
但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。
您的朋友Bill必须知道地图的总面积。
你自告奋勇写了一个计算这个总面积的程序。
输入格式
输入包含多组测试用例。
对于每组测试用例，第一行包含整数n，表示总的地图数量。
接下来n行，描绘了每张地图，每行包含四个数字x1,y1,x2,y2x1,y1,x2,y2（不一定是整数）,(x1,y1)(x1,y1)和(x2,y2)(x2,y2)分别是地图的左上角位置和右下角位置。
当输入用例n=0时，表示输入终止，该用例无需处理。
输出格式
每组测试用例输出两行。
第一行输出”Test case #k”，其中k是测试用例的编号，从1开始。
第二行输出“Total explored area：a”，其中a是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。
在每个测试用例后输出一个空行。
数据范围
1≤n≤100,
0≤x10≤y1
输入样例：
2
10 10 20 20
15 15 25 25.5
0
输出样例：
Test case #1
Total explored area: 180.00
题意：求面积并
题解：扫描线。
如果题目给出的矩形如下：
那么我们要求的总面积为：
我们如果用一条竖直的直线从左到右扫过整个坐标系，那么直线上在所求面积中的覆盖长度L只会在每个矩形的左右边界发生变化，整个图形可以被分成2*n段，每一段直线被覆盖的长度L都是固定的，这一段的面积为L*?x。
我们知道?x是两个相邻的x之间的间距，那我们要怎么维护每一段L的长度？
对于每个矩形，我们把左边界记为一个四元组：(x1,y1,y2,1)，把右边界记为(x2,y1,y2,-1)(假设x1
代码：
#include using namespace std;
#define ll long long
const int N = 200 + 10;
struct node{
double x,y1,y2;
int val;
node() {}
node(double x, double y1, double y2,int val){
this->x = x; this->val = val;
this->y1 = y1; this->y2 = y2;
}
bool operator const node &t)const {
return xt.x;
}
};
struct Tree{
int l,r,cnt;
double len;
}t[N3]; //找了一个小时的段错误，结果是*4小了？？？
int n,k=1;
vector a;
vectordouble> y;
void up(int rt) {
if (t[rt].cnt>0) t[rt].len = y[t[rt].r+1] - y[t[rt].l];
else t[rt].len = t[rt1].len + t[rt1|1].len;
}
void build(int rt,int l,int r) {
t[rt].l = l,t[rt].r = r; t[rt].cnt = 0;
t[rt].len = 0;
if (l == r) return;
int mid = (l+r)>>1;
build(rt1,l,mid);
build(rt1|1,mid+1,r);
}
void update(int rt,int l,int r,int val) {
if (l = t[rt].r) {
t[rt].cnt+=val;
up(rt);
return;
}
int mid = (t[rt].l+t[rt].r)>>1;
if (l 1,l,r,val);
if (r > mid) update(rt1|1,l,r,val);
up(rt);
}
int main() {
while (~scanf("%d",&n) && n) {
y.clear();a.clear();
for(int i = 0; i ) {
double x1,x2,y1,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
y.push_back(y1);
y.push_back(y2);
a.push_back(node(x1,y2,y1,1));
a.push_back(node(x2,y2,y1,-1));
}
y.push_back(-1);
sort(a.begin(),a.end());
sort(y.begin(),y.end());
y.erase(unique(y.begin(),y.end()),y.end());
int m = y.size(),num = a.size();
build(1,0,m);
double ans = 0;
for (int i = 0; i ) {
int l = lower_bound(y.begin(),y.end(),a[i].y2)-y.begin();
int r = lower_bound(y.begin(),y.end(),a[i].y1) - y.begin()-1;
update(1,l,r,a[i].val);
ans += t[1].len*(a[i+1].x-a[i].x);
}
printf("Test case #%d\n",k++);
printf("Total explored area: %.2f\n\n",ans);
}
return 0;
}
View Code
PS：不知道为什么我的线段树数组定义大小*4了还会段错误？？？
AcWing 247. 亚特兰蒂斯 | 扫描线
标签：std 数字 onclick 面积并 xpl pre ase ++ 固定
原文地址：https://www.cnblogs.com/l999q/p/11366840.html