汽车建设网站,网站备案加急,企业网站带数据库,wordpress做自建站卫星覆盖#xff08;NOI1997#xff09;
题面#xff1a;
SERCOI#xff08;Space-Earth Resource Cover-Observe lnstitute#xff09; 是一个致力于利用卫星技术对空间和地球资源进行覆盖观测的组织。现在他们研制成功一种新型资源观测卫星 -SERCOI-308。这种卫星可以…卫星覆盖NOI1997
题面
SERCOISpace-Earth Resource Cover-Observe lnstitute 是一个致力于利用卫星技术对空间和地球资源进行覆盖观测的组织。现在他们研制成功一种新型资源观测卫星 -SERCOI-308。这种卫星可以覆盖空间直角坐标系中一定大小的立方体空间卫星处于该立方体的中心。 其中 x,y,zx,y,z 为立方体的中心点坐标 rr 为此中心点到立方体各个面的距离即 rr 为立方体高的一半立方体的各条边均平行于相应的坐标轴。我们可以用一个四元组 (x,y,z,r)(x,y,z,r) 描述一颗卫星的状态它所能覆盖的空间体积 。 由于一颗卫星所能覆盖的空间体积是有限的因此空间中可能有若干颗卫星协同工作。它们所覆盖的空间区域可能有重叠的地方如下图所示阴影部分表示重叠的区域。 写一个程序根据给定的卫星分布情况计算它们所覆盖的总体积。 思路
第一道自己做的NOI的题。
说白了就是求三维立方体的覆盖体积。
我们继承我们二维的思想也就是用扫描线和线段树来求矩形的面积并。
扩展到三维上也就是我们把他分割成很多高度为一的层然后对于每一个层去做二维的面积并。
然后答案就是每一个层的二维面积并的和。
时间复杂度。
代码
#include bits/stdc.h
using namespace std;
const int N 100010;
int n;
struct owl{int x,y1,y2;int k;bool operator (const owl t)const{return x t.x;}
}seg[N * 2];
struct hoot{int l,r;int cnt;int len;
}tr[N * 8];
vectorintys;
int find(int y){return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}
void pushup(int u){if (tr[u].cnt){tr[u].len ys[tr[u].r 1] - ys[tr[u].l];}else if (tr[u].l ! tr[u].r){tr[u].len tr[u 1].len tr[u 1 | 1].len;}else{tr[u].len 0;}
}
void build(int u,int l,int r){tr[u] {l,r,0,0};if (l ! r){int mid l r 1;build(u 1,l,mid),build(u 1 | 1,mid 1,r);}
}
void modify(int u,int l,int r,int k){if (tr[u].l l tr[u].r r){tr[u].cnt k;pushup(u);}else{int mid tr[u].l tr[u].r 1;if (l mid){modify(u 1,l,r,k);}if (r mid){modify(u 1 | 1,l,r,k);}pushup(u);}
}
struct DID{int x,y,z,d;
}v[N];
struct SOREN{int x1,y1,x2,y2;
};
int main(){cin n;for (int i 1; i n; i ){cin v[i].x v[i].y v[i].z v[i].d;}int ans 0;for (int Z -1000; Z 1000; Z ){ys.clear();int m 0;vectorSORENvec;for (int i 1; i n; i ){int x1 -3000, y1 -3000, x2 -3000, y2 -3000;if (Z v[i].z - v[i].d 1 Z v[i].z v[i].d){x1 v[i].x - v[i].d,x2 v[i].x v[i].d;y1 v[i].y - v[i].d,y2 v[i].y v[i].d;}if (x1 -3000 y1 -3000 x2 -3000 y2 -3000){continue;}seg[m ] {x1, y1, y2, 1};seg[m ] {x2, y1, y2, -1};vec.push_back({x1,y1,x2,y2});ys.push_back(y1), ys.push_back(y2);}if (vec.size() 1){ans (vec[0].x2 - vec[0].x1) * (vec[0].y2 - vec[0].y1);continue;}if (m 0){sort(ys.begin(), ys.end());ys.erase(unique(ys.begin(), ys.end()), ys.end());build(1, 0, ys.size() - 2);sort(seg, seg m);int res 0;for (int i 0; i m; i ){if (i 0){res (tr[1].len) * (seg[i].x - seg[i - 1].x);}modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);}ans res;}}cout ans;return 0;
}
