首页 > 代码库 > HDU 1542 Atlantis 线段树+离散化+扫描线
HDU 1542 Atlantis 线段树+离散化+扫描线
题意:给出一些矩形的最上角坐标和右下角坐标,求这些矩形的面积并。
NotOnlySuccess 线段树专辑中扫描线模板题,弱智的我对着大大的代码看了一下午才搞懂。 具体见思路见注释=。=
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define lson rt<<1,l,mid#define rson rt<<1|1,mid + 1,rusing namespace std;const int maxn = 4004;struct Seg { double l, r, x; int cover; Seg(double l, double r, double x, int cover) :l(l), r(r), x(x), cover(cover) {} //排序大小按照x轴的坐标大小 bool operator < (const Seg &tmp) const { return x < tmp.x; }};int n, cnt[maxn << 2];double len[maxn << 2];vector<double> dy;vector<Seg> seg;int GetID(double Val) { //二分查找点的坐标,离散化 return lower_bound(dy.begin(), dy.end(), Val) - dy.begin();}void pushup(int rt, int l, int r) { int lc = rt << 1, rc = rt << 1 | 1; //如果当前线段存在,更新坐标 //这里r+1是因为长度为x的线段有x+1个点,所以最后一个点是r+1 if (cnt[rt]) len[rt] = dy[r + 1] - dy[l]; else if (r == l) len[rt] = 0; else len[rt] = len[lc] + len[rc];}void update(int rt, int l, int r, int ql, int qr, int Val) { int lc = rt << 1, rc = rt << 1 | 1, mid = (l + r) >> 1; if (ql <= l && qr >= r) { //累加当前线段的值 cnt[rt] += Val; pushup(rt, l, r); } else { //标记不需要下放,因为当前线段的增减和子线段没有关系 //而且每条线段必定增加一次,减少一次 if (ql <= mid) update(lson, ql, qr, Val); if (qr > mid) update(rson, ql, qr, Val); pushup(rt, l, r); }}int main() { int kase = 1; while (scanf("%d", &n),n != 0) { //初始化线段树 dy.clear(); seg.clear(); memset(cnt, 0, sizeof(cnt)); memset(len, 0, sizeof(len)); //读入数据 for (int i = 1; i <= n; i++) { double x1, x2, y1, y2; scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); //将每个矩形抽象成两条线段 seg.push_back(Seg(y1, y2, x1, 1)); seg.push_back(Seg(y1, y2, x2, -1)); //存储每个坐标的值 dy.push_back(y1); dy.push_back(y2); } //将浮点坐标离散化 sort(dy.begin(), dy.end()); dy.erase(unique(dy.begin(), dy.end()), dy.end()); //将线段排序 sort(seg.begin(), seg.end()); int msize = seg.size(), k = dy.size(); double ret = 0; for (int i = 0; i < msize - 1; i++) { //这里的qr为什么要减一? 是因为我线段树每个节点存的是l,r之间的线段,而不是点集,把每个线段当成点来看的话, //每个[l,r]的点构成的线段编号应该是[l,r-1] int ql = GetID(seg[i].l), qr = GetID(seg[i].r) - 1; //更新值 update(1, 0, k - 1, ql, qr, seg[i].cover); //累加当前扫描线扫过的面积 ret += len[1] * (seg[i + 1].x - seg[i].x); } printf("Test case #%d\nTotal explored area: %.2lf\n\n", kase++, ret); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。