首页 > 代码库 > HDU1542Atlantis(扫描线)
HDU1542Atlantis(扫描线)
HDU1542Atlantis(扫描线)
题目链接
题目大意:给你n个覆盖矩形,问最后覆盖的面积。
解题思路:将每一个矩形拆成两条线段,一条是+1的,还有一条是减1的。然后扫描先从上往下扫描,碰到加1的那条线段,那么这条线段范围内的节点的覆盖信息就+1,直到碰到减1这个线段范围内的节点的覆盖信息都须要减1。
这样说可能理解不了,就能够画画矩形然后画下扫描线在理解理解。然后就是须要离散化的建树,由于这里是都double型的。所谓离散化建树的意思就是如今每一个叶子节点代表的是一段区间。而不是单独的一点。
代码:
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 205;
#define lson(x) (x<<1)
#define rson(x) ((x<<1) | 1)
struct Node {
int l, r, add;
double s;
void set (int l, int r, double s, int add) {
this->l = l;
this->r = r;
this->s = s;
this->add = add;
}
}node[4 * maxn];
struct Line {
double x, y1, y2;
int flag;
Line (double x, double y1, double y2, int flag) {
this->x = x;
this->y1 = y1;
this->y2 = y2;
this->flag = flag;
}
bool operator < (const Line &l) const {
return x < l.x;
}
};
int n;
vector<Line> L;
vector<double> pos;
void pushup(int u) {
if (node[u].add)
node[u].s = pos[node[u].r + 1] - pos[node[u].l];
else if (node[u].l == node[u].r)
node[u].s = 0;
else
node[u].s = node[lson(u)].s + node[rson(u)].s;
}
void build (int u, int l, int r) {
node[u].set (l, r, 0, 0);
if (l == r)
return;
int m = (l + r)>>1;
build(lson(u), l, m);
build(rson(u), m + 1, r);
}
void update (int u, int l, int r, int v) {
if (node[u].l >= l && node[u].r <= r) {
node[u].add += v;
pushup(u);
return;
}
int m = (node[u].l + node[u].r)>>1;
if (l <= m)
update (lson(u), l, r, v);
if (r > m)
update (rson(u), l, r, v);
pushup(u);
}
void init () {
pos.clear();
L.clear();
double x1, y1, x2, y2;
for (int i = 0; i < n; i++) {
scanf ("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
pos.push_back(y1);
pos.push_back(y2);
L.push_back(Line(x1, y1, y2, 1));
L.push_back(Line(x2, y1, y2, -1));
}
sort (pos.begin(), pos.end());
sort (L.begin(), L.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
build(1, 0, (int)pos.size() - 1);
}
double solve() {
init();
double ans = 0;
for (int i = 0; i < (int)L.size() - 1; i++) {
int l = lower_bound(pos.begin(), pos.end(), L[i].y1) - pos.begin();
int r = lower_bound(pos.begin(), pos.end(), L[i].y2) - pos.begin();
update (1, l, r - 1, L[i].flag);
// printf ("%.2lf\n", node[1].s);
ans += node[1].s * (L[i + 1].x - L[i].x);
}
return ans;
}
int main () {
int T = 0;
double x1, y1, x2, y2;
while (scanf ("%d", &n) && n) {
printf ("Test case #%d\n", ++T);
printf ("Total explored area: %.2lf\n\n", solve());
}
return 0;
}
HDU1542Atlantis(扫描线)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。