（CSP2019模拟）DTOJ 4629. 世界

本文主要是介绍（CSP2019模拟）DTOJ 4629. 世界，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

有一个虚无的结界，隔开了两个世界。

人们在结界内游荡，而远方的星辰在结界外。

我们可以把结界看作 $x$ 轴，那么人们都在 $x$ 轴下方，而星星都在 $x$ 轴上方。

人们本应该能看到所有的星星，但是结界外( $x$ 轴上方)出现了几座墙，挡住了人们的视线。墙是平行于 $x$ 轴的。

现在想问，每个人分别能看到多少星星。

测试点编号	$n$	$m$	$q$
1~3	$\le 1000$	$\le 5$	$\le 1000$
4~6	$\le 40000$	$=1$	$\le 40000$
7~10	$\le 40000$	$\le 5$	$\le 40000$

题解

先考虑m=1的情况，即计算每个人在一个角度范围内的星星数，但每个人的位置不同，故考虑映射到一条公共的直线——x轴上。于是算出人、星星和墙端点的直线与x轴的交点，即映射到一段区间上，对于一个人，一个星星被挡住，当且仅当星星映射的区间完全包含人的区间，于是转为一个二维偏序问题。
注意到m很小，考虑枚举墙的集合，但这样会算重，那么每次计算出一定被这个集合的所有墙都挡住的星星数，容斥一下即可。对于多堵墙，考虑一个星星要被所有的墙对于一个人被挡住的条件，先求出墙的最高位置和人的视角范围的交集，那么在这个交集中的星星映射的区间一定都包含这个交集，否则一定存在不包含的，即星星映射的交集完全包含人映射的交集，于是又转化为一个二维偏序问题。

这篇关于（CSP2019模拟）DTOJ 4629. 世界的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---