当前位置: 首页 > article >正文

线段树例题题解

卫星覆盖(NOI1997)

题面:

SERCOI(Space-Earth Resource Cover-Observe lnstitute) 是一个致力于利用卫星技术对空间和地球资源进行覆盖观测的组织。现在他们研制成功一种新型资源观测卫星 -SERCOI-308。这种卫星可以覆盖空间直角坐标系中一定大小的立方体空间,卫星处于该立方体的中心。 其中 (x,y,z)(x,y,z) 为立方体的中心点坐标, rr 为此中心点到立方体各个面的距离(即 rr 为立方体高的一半).立方体的各条边均平行于相应的坐标轴。我们可以用一个四元组 (x,y,z,r)(x,y,z,r) 描述一颗卫星的状态,它所能覆盖的空间体积 。 由于一颗卫星所能覆盖的空间体积是有限的,因此空间中可能有若干颗卫星协同工作。它们所覆盖的空间区域可能有重叠的地方,如下图所示(阴影部分表示重叠的区域)。

写一个程序,根据给定的卫星分布情况,计算它们所覆盖的总体积。

思路

第一道自己做的NOI的题。

说白了就是求三维立方体的覆盖体积。

我们继承我们二维的思想,也就是用扫描线和线段树来求矩形的面积并。

扩展到三维上,也就是我们把他分割成很多高度为一的层,然后对于每一个层去做二维的面积并。

然后答案就是每一个层的二维面积并的和。

时间复杂度:\Theta(n^2\log n)

代码

#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];
vector<int>ys;
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;
		vector<SOREN>vec;
		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; 
}

http://www.kler.cn/a/459931.html

相关文章:

  • 高频java面试题
  • 【Rust自学】9.3. Result枚举与可恢复的错误 Pt.2:传播错误、?运算符与链式调用
  • Linux-掉电保护方案
  • Oracle 23ai 图形界面安装
  • 迅为RK3568开发板编译Android12源码包-设置屏幕配置
  • 【Vue】获取el-select修改前后的数据
  • Linux ACM 驱动程序
  • 【UE5】UnrealEngine源码构建2:windows构建unreal engine 5.3.2
  • Kali Linux系统上配置Git的全局代理
  • CentOS中使用SSH远程登录
  • STM32F103 I2C软件模拟(AT24C02)
  • 如何用Python爬取网站数据:基础教程与实战
  • 【AIGC-ChatGPT职业提示词指令】智能职业规划助手:基于SVG可视化的职业发展指南系统
  • JVM实战—3.JVM垃圾回收的算法和全流程
  • ubuntu18.04使用ndk编译protobuf库
  • Kafka数据迁移全解析:同集群和跨集群
  • 记一次 .NET某电商医药网站 CPU爆高分析
  • MySQL 可重复读隔离级别,完全解决幻读了吗?
  • uniapp 微信小程序开发使用高德地图、腾讯地图
  • Excel基础知识
  • 命令行之巅:Linux Shell编程的至高艺术(中)
  • 加强版十六章视频读写
  • Oracle SqlPlus常用命令简介
  • SDL2音视频播放的常用API库
  • Redis字符串底层结构对数值型的支持常用数据结构和使用场景
  • 安装torch-geometric库