UVa 1042 Lots of Sunlight

题目描述公寓建筑管理公司ACM\texttt{ACM}ACM在上海郊区拥有若干高层公寓楼。由于这些公寓能接收到更多直射阳光公司希望向潜在住户精确告知某间公寓在2005\texttt{2005}2005年4\texttt{4}4月6\texttt{6}6日的日照时段。该日日出时间为5:37\texttt{5:37}5:37日落时间为18:17\texttt{18:17}18:17。公寓楼呈东西方向一字排开楼号从东到西依次为01,02,…\texttt{01}, \texttt{02}, \dots01,02,…。公寓编号的后两位表示楼号其余高位数字表示楼层1\texttt{1}1为地面层。太阳从东方升起以恒定角速度沿天空划过直到西方落下。唯一可能产生阴影的是建筑物本身每栋楼可能在其东侧或西侧的楼上投下阴影。当公寓的东墙或西墙被阳光完全覆盖或太阳位于正头顶时该公寓被认为接收到阳光。输入格式输入包含多组公寓小区描述。每组描述以一行整数nnn1≤n1001 \le n 1001≤n100开头表示公寓楼数量。下一行有两个整数www东西方向宽度和hhh每层高度单位均为米。接下来是一行整数m(1),d(1),m(2),d(2),…,d(n−1),m(n)m(1), d(1), m(2), d(2), \ldots, d(n-1), m(n)m(1),d(1),m(2),d(2),…,d(n−1),m(n)其中m(i)m(i)m(i)表示第iii栋楼的公寓层数d(i)d(i)d(i)表示第iii栋楼与第i1i1i1栋楼之间的水平距离米。小区描述之后是一个整数列表表示待查询的公寓编号以0\texttt{0}0结束。整个输入文件以单独一行0\texttt{0}0结束。输出格式对于每组小区描述首先输出Apartment Complex: 编号。对于每个查询输出对应的日照时间段格式为HH:MM:SS - HH:MM:SS时间向下取整到秒。若查询的公寓不存在输出Apartment 编号: Does not exist。具体格式见样例。样例样例输入3 6 4 5 6 3 3 4 302 401 601 303 0 4 5 3 4 5 7 8 5 4 3 101 302 503 0 0样例输出Apartment Complex: 1 Apartment 302: 10:04:50 - 13:23:47 Apartment 401: 05:37:00 - 17:13:57 Apartment 601: Does not exist Apartment 303: 09:21:19 - 18:17:00 Apartment Complex: 2 Apartment 101: 05:37:00 - 12:53:32 Apartment 302: 09:08:55 - 14:52:47 Apartment 503: 09:01:12 - 18:17:00题目分析本题的核心是计算给定公寓在一天内被阳光照射的连续时段。由于太阳运动规律已知恒定角速度且唯一遮挡物是其他建筑因此可以将问题转化为几何遮挡判定。将建筑视为东西向延伸的矩形截面每栋楼的高度由其楼层数乘以层高决定。公寓的某一面墙东墙或西墙是否被完全照亮取决于是否存在更东或更西的建筑其顶部投影是否覆盖到该墙的底部。若某遮挡建筑的顶部投影高度大于等于该墙底部高度则墙面被完全遮挡反之则完全照亮。太阳高度角随从日出经过的时间单调变化上午增加下午减少。对于上午时段太阳在东侧公寓的东墙接受阳光只有东边的建筑可能遮挡下午时段则相反西墙接受阳光只有西边的建筑可能遮挡。正午太阳在头顶任何建筑都不会产生阴影因此所有公寓在正午时刻必定有阳光。解题思路设从日出时刻开始计时的秒数为ttt总日照时长T45600T 45600T45600秒从5:37\texttt{5:37}5:37到18:17\texttt{18:17}18:17。太阳高度角的正切值ρ\rhoρ与ttt的关系为上午0≤t≤T/20 \le t \le T/20≤t≤T/2ρtan⁡(πtT)\rho \tan\left(\frac{\pi t}{T}\right)ρtan(Tπt​)下午T/2≤t≤TT/2 \le t \le TT/2≤t≤Tρtan⁡(π(T−t)T)\rho \tan\left(\frac{\pi (T-t)}{T}\right)ρtan(Tπ(T−t)​)对于某一遮挡建筑jjj其顶部相对于目标公寓某墙底部的高度差为ΔHHj−yfloor\Delta H H_j - y_{\text{floor}}ΔHHj​−yfloor​若为负则视为000水平距离为LLL。当太阳高度角的正切值ρ≥ΔHL\rho \ge \frac{\Delta H}{L}ρ≥LΔH​时太阳光线高于建筑顶部阴影无法到达目标墙底部墙面被照亮反之则被遮挡。因此对于目标公寓的东墙只需考虑所有jbuildingj \textit{building}jbuilding的建筑求出ΔHL\frac{\Delta H}{L}LΔH​的最大值RER_ERE​。若RE0R_E 0RE​0说明没有任何遮挡东墙从日出即被照亮否则东墙被照亮的起始时刻tstartt_{\text{start}}tstart​满足πtstartTarctan⁡(RE)\frac{\pi t_{\text{start}}}{T} \arctan(R_E)Tπtstart​​arctan(RE​)即tstartTπarctan⁡(RE)t_{\text{start}} \frac{T}{\pi}\arctan(R_E)tstart​πT​arctan(RE​)。类似地对于西墙考虑所有jbuildingj \textit{building}jbuilding的建筑求得最大比值RWR_WRW​。西墙被照亮的结束时刻tendt_{\text{end}}tend​满足π(T−tend)Tarctan⁡(RW)\frac{\pi (T - t_{\text{end}})}{T} \arctan(R_W)Tπ(T−tend​)​arctan(RW​)即tendT−Tπarctan⁡(RW)t_{\text{end}} T - \frac{T}{\pi}\arctan(R_W)tend​T−πT​arctan(RW​)。由于正午太阳在头顶实际日照区间必须包含T/2T/2T/2因此需要做边界裁剪tstart≤T/2≤tendt_{\text{start}} \le T/2 \le t_{\text{end}}tstart​≤T/2≤tend​。最终将tstartt_{\text{start}}tstart​和tendt_{\text{end}}tend​加上日出秒数向下取整到秒即得到绝对时间。代码实现// Lots of Sunlight// UVa ID: 1042// Verdict: Accepted// Submission Date: 2026-07-21// UVa Run Time: 0.040s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoublePIacos(-1.0);constintTOTAL_SEC45600;constintSUNRISE_SEC5*360037*60;constintSUNSET_SEC18*360017*60;intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcomplexId0;while(true){intn;cinn;if(n0)break;complexId;intw,h;cinwh;vectorintm(n1),d(n1);for(inti1;in;i){if(in)cinm[i]d[i];elsecinm[i];}vectordoubleeast(n1),west(n1);east[1]0.0;west[1]w;for(inti2;in;i){east[i]west[i-1]d[i-1];west[i]east[i]w;}coutApartment Complex: complexId\n;while(true){intquery;cinquery;if(query0)break;intbuildingquery%100,floorsquery/100;if(building1||buildingn||floors1||floorsm[building]){coutApartment query: Does not exist\n;continue;}doublemaxRatioE0.0;doublemaxRatioW0.0;for(intj1;jbuilding;j){doubledisteast[building]-west[j];intheightDiffm[j]*h-(floors-1)*h;if(heightDiff0)continue;doubleratioheightDiff/dist;if(ratiomaxRatioE)maxRatioEratio;}for(intjbuilding1;jn;j){doubledisteast[j]-west[building];intheightDiffm[j]*h-(floors-1)*h;if(heightDiff0)continue;doubleratioheightDiff/dist;if(ratiomaxRatioW)maxRatioWratio;}doubletStart(maxRatioE0.0)?0.0:(TOTAL_SEC/PI)*atan(maxRatioE);doubletEnd(maxRatioW0.0)?(double)TOTAL_SEC:TOTAL_SEC-(TOTAL_SEC/PI)*atan(maxRatioW);if(tStart0)tStart0;if(tStartTOTAL_SEC/2.0)tStartTOTAL_SEC/2.0;if(tEndTOTAL_SEC/2.0)tEndTOTAL_SEC/2.0;if(tEndTOTAL_SEC)tEndTOTAL_SEC;autoformatTime[](doublet){inttotal(int)floor(t1e-7)SUNRISE_SEC;inthhtotal/3600,mm(total%3600)/60,sstotal%60;coutsetw(2)setfill(0)hh:setw(2)setfill(0)mm:setw(2)setfill(0)ss;};coutApartment query: ;formatTime(tStart);cout - ;formatTime(tEnd);cout\n;}}return0;}总结本题的关键在于将物理遮挡转化为几何比值比较避免频繁调用反三角函数。通过预计算建筑坐标将查询复杂度降至O(n)O(n)O(n)。处理距离为0\texttt{0}0的边界情况时除法会产生无穷大而atan\texttt{atan}atan能正确处理。最终输出需注意向下取整和边界裁剪确保日照区间包含正午时刻。该解法兼顾了正确性与高效性适用于题目给定的n100n 100n100的规模。