凡科建站网,哪里有网站制作服务,怎么做自己的微信小程序,在线网站建设哪个正规Picture POJ - 1177
题目#xff1a;
多个矩阵相交在一起#xff0c;问新图形的周长是多少
题解#xff1a;
参考题解 周长分为两部分#xff1a;横线和竖线 横线计算方法#xff1a;现在总区间被覆盖的长度和上一次总区间被覆盖的长度之差的绝对值 那么我们只需要从…Picture POJ - 1177
题目
多个矩阵相交在一起问新图形的周长是多少
题解
参考题解 周长分为两部分横线和竖线 横线计算方法现在总区间被覆盖的长度和上一次总区间被覆盖的长度之差的绝对值 那么我们只需要从上往下再从左往右扫描两次即可 但是这样需要两次有没有更简化的方法 现在我们打算一次自上而下的扫描把横线竖线都算出来 横线的算法和上面说的方法一样现在这次总区间被覆盖的长度和上一次总区间被覆盖的长度之差的绝对值 我们用线段树来记录一些信息
l,r 该节点代表的线段的左右端点坐标len:这个区间被覆盖的长度(即计算时的有效长度)s:表示这个区间被覆盖率多次lc,rc标记这个节点的左右两个端点是否被覆盖(0表示没有1表示有)sum表示这个区间有多少条不连续的线段
注意这个sum涉及到了竖线的计算 若区间[0,10]被[1,2][4,5]覆盖则num 2
若区间[0,10]被[1,3][4,5]覆盖则num 1两区间刚好连在一起
若区间[0,10]被[1,5][2,6]覆盖则num 1两区间连起来还是一段 这样就可以计算竖线 竖线的长度【下一条即将被扫到的横线的高度 - 现在扫到的横线的高度】* 2 * num 乘2是因为每条线段有两个端点 有num个不相交的横线向下划动h不就形成长度为h的2 * num个竖线
代码
#include algorithm
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define ls i 1
#define rs i 1 | 1
#define m(i) ((tr[i].l tr[i].r) 1)
typedef long long ll;
const int N 5007;
const int X 20007;
const int inf 1 29;
struct Edge
{int l, r;int h;int f;bool operator(const Edge a) const{return h a.h;}
} edge[N * 2];
struct tree
{int l, r;int len;int s;bool lc, rc; //表示这个节点代表的区间左右两个端点是否被覆盖int num; //这个区间有多少不连续到线段
} tr[X * 4];
void pushup(int i)
{if (tr[i].s) {tr[i].len tr[i].r - tr[i].l 1;tr[i].lc tr[i].rc 1;tr[i].num 1;}else if (tr[i].l tr[i].r) {tr[i].len 0;tr[i].lc tr[i].rc 0;tr[i].num 0;}else {tr[i].len tr[ls].len tr[rs].len;tr[i].lc tr[ls].lc;tr[i].rc tr[rs].rc;tr[i].num tr[ls].num tr[rs].num - (tr[ls].rc tr[rs].lc);}
}
void build(int i, int l, int r)
{tr[i].l l;tr[i].r r;tr[i].s tr[i].len 0;tr[i].lc tr[i].rc tr[i].num 0;if (l r)return;int mid m(i);build(ls, l, mid);build(rs, mid 1, r);
}
void update(int i, int l, int r, int xx)
{if (l tr[i].l tr[i].r r) {tr[i].s xx;pushup(i);return;}int mid m(i);if (r mid)update(ls, l, r, xx);else if (l mid)update(rs, l, r, xx);else {update(ls, l, mid, xx);update(rs, mid 1, r, xx);}pushup(i);
}
int main()
{int n;while (scanf(%d, n) ! EOF) {int x1, x2, y1, y2, mx -inf, mn inf;int tot 0;for (int i 0; i n; i) {scanf(%d%d%d%d, x1, y1, x2, y2);mx max(mx, max(x1, x2));mn min(mn, min(x1, x2));Edge t1 edge[tot];Edge t2 edge[tot 1];t1.l t2.l x1;t1.r t2.r x2;t1.h y1;t1.f 1;t2.h y2;t2.f -1;tot 2;}sort(edge, edge tot);//数据小不用离散化int ans 0;int last 0;build(1, mn, mx - 1);for (int i 0; i tot; i) {update(1, edge[i].l, edge[i].r - 1, edge[i].f);ans abs(tr[1].len - last);ans (edge[i 1].h - edge[i].h) * 2 * tr[1].num;last tr[1].len;}printf(%d\n, ans);}return 0;
}
