UVa 12323 Inspecting Radars

题目描述Radars Inc.\texttt{Radars Inc.}Radars Inc.是一家世界知名的雷达制造商其卓越声誉源于严格的质量保证流程以及适合各种预算的多种雷达型号。公司雇佣你来开发一项详细的检测程序该程序由一系列EEE个实验组成针对某一特定监视型号。检测区域用极坐标平面表示平面上有NNN个物体位于整数极坐标位置。被检测的雷达模型位于原点(0,0)(0,0)(0,0)能够探测距离小于其探测范围RRR的物体扫描区域由四个调节参数α\alphaα、AAA、hhh、HHH定义。形式化地雷达的扫描区域为极坐标点集合{(r,θ)∣h≤rhH, α≤θ≤αA} \{(r,\theta)\mid h \le r hH,\; \alpha \le \theta \le \alphaA\}{(r,θ)∣h≤rhH,α≤θ≤αA}其中α,A,h,H\alpha, A, h, Hα,A,h,H均为整数α\alphaα扫描起始角度0≤α3600 \le \alpha 3600≤α360AAA扫描开角0≤A3600 \le A 3600≤A360hhh内半径0≤hR0 \le h R0≤hRHHH径向厚度1≤H≤R1 \le H \le R1≤H≤R。物体(r,θ)(r,\theta)(r,θ)会被雷达显示当且仅当h≤rhHh \le r hHh≤rhH且α≤θ≤αA\alpha \le \theta \le \alphaAα≤θ≤αA其中角度不等式按模360∘360^\circ360∘理解即在圆周上比较角度。给定平面上NNN个物体你需要通过EEE个特定参数设置的实验来检测雷达模型。每个实验中参数HHH和AAA固定而α\alphaα0≤α3600 \le \alpha 3600≤α360和hhh0≤hR0 \le h R0≤hR可以自由选择为整数要求计算出雷达最多能显示多少个物体。输入格式输入包含多个测试用例。每个测试用例描述如下第一行两个整数NNN和RRR分别表示物体数量和探测范围1≤N≤1041 \le N \le 10^41≤N≤1042≤R≤1022 \le R \le 10^22≤R≤102。接下来NNN行每行两个整数rir_iri​和θi\theta_iθi​表示第iii个物体的极坐标1≤riR1 \le r_i R1≤ri​R0≤θi3600 \le \theta_i 3600≤θi​360。下一行一个整数EEE表示实验数量1≤E≤1021 \le E \le 10^21≤E≤102。接下来EEE行每行两个整数HjH_jHj​和AjA_jAj​表示第jjj个实验的固定厚度和开角1≤Hj≤R1 \le H_j \le R1≤Hj​≤R0≤Aj3600 \le A_j 3600≤Aj​360。保证同一测试用例中不存在两个物体位于相同的整数极坐标。输入以一行0 0结束。输出格式对于每个测试用例输出EEE行第jjj行表示第jjj个实验下雷达最多能显示的物体数量。样例输入6 100 15 7 15 60 40 15 50 15 45 30 45 90 2 2 1 100 359 9 100 15 7 15 60 40 15 50 15 45 30 45 90 40 45 50 45 78 100 6 100 359 11 30 10 30 11 29 5 30 11 10 0 0输出1 6 9 5 3 3 2 2题目分析对于给定的实验参数HHH和AAA我们需要选择内半径hhh和起始角度α\alphaα使得落在扫描区域内的物体数量最多。雷达显示的条件可以分解为两个独立的条件半径条件h≤rhHh \le r hHh≤rhH和角度条件α≤θ≤αA\alpha \le \theta \le \alphaAα≤θ≤αA模360∘360^\circ360∘。注意到hhh和α\alphaα的选择是相互独立的因此我们可以枚举所有可能的hhh然后在每个hhh下只考虑半径满足条件的物体再在角度维度上求一个长度为A1A1A1的连续环形区间内的最大物体数。最终答案即为所有hhh下该最大值中的最大者。由于RRR最大只有100100100而角度范围固定为360360360因此枚举所有hhh并逐区间统计是完全可行的。每个实验的复杂度约为O(R⋅(N360))O(R \cdot (N 360))O(R⋅(N360))在给定限制下可以轻松通过。解题思路数据预处理对于每个测试用例我们将物体按半径分组存储。因为R≤100R \le 100R≤100可以创建一个大小为RRR的数组每个元素是一个列表存放该半径上所有物体的角度值。这样在枚举hhh时可以快速获取半径落在[h,hH)[h, hH)[h,hH)内的所有物体。枚举内半径hhh对于每个可能的hhh0≤hR0 \le h R0≤hR执行以下步骤清空一个长度为360360360的计数数组cnt\textit{cnt}cntcnt[θ]\textit{cnt}[\theta]cnt[θ]表示当前半径区间内角度为θ\thetaθ的物体个数。遍历半径rrr从hhh到min⁡(R−1,hH−1)\min(R-1, hH-1)min(R−1,hH−1)将该半径上所有物体的角度累加到cnt\textit{cnt}cnt中。现在问题转化为在环形数组cnt[0…359]\textit{cnt}[0 \ldots 359]cnt[0…359]上寻找一个长度为WA1W A1WA1的连续区间因为角度包含两端所以区间包含的整数角度数为A1A1A1使得区间内元素和最大。环形窗口最大值为了处理环形我们将cnt\textit{cnt}cnt复制一遍得到长度为720720720的数组doubled\textit{doubled}doubled其中doubled[i]cnt[i mod 360]\textit{doubled}[i] \textit{cnt}[i \bmod 360]doubled[i]cnt[imod360]。然后在doubled\textit{doubled}doubled上滑动一个长度为WWW的窗口起始位置从000到359359359这样覆盖所有可能的起始角度取窗口和的最大值。特殊情况如果W≥360W \ge 360W≥360即A≥359A \ge 359A≥359则窗口覆盖整个圆周此时最大值为cnt\textit{cnt}cnt的总和。更新答案对于每个实验我们得到所有hhh下的最大值输出即可。复杂度分析对于每个实验枚举hhh的次数为RRR最多100100100。每个hhh需要统计半径区间内的物体所有hhh的总统计量为O(R⋅N)O(R \cdot N)O(R⋅N)因为每个物体可能被多个hhh统计到但RRR很小总统计次数为O(N⋅R)O(N \cdot R)O(N⋅R)最坏104×10010610^4 \times 100 10^6104×100106。滑动窗口计算为O(360)O(360)O(360)。单次实验复杂度O(R⋅NR⋅360)O(R \cdot N R \cdot 360)O(R⋅NR⋅360)总实验数E≤100E \le 100E≤100最坏总复杂度约100×(1063.6×104)≈108100 \times (10^6 3.6 \times 10^4) \approx 10^8100×(1063.6×104)≈108在222秒内可行实际常数很小。代码实现// Inspecting Radars// UVa ID: 12323// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.260s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN,R;while(cinNR){if(N0R0)break;// 按半径分组存储每个物体角度vectorvectorintbyRadius(R);// 半径 0 ~ R-1实际物体半径 1for(inti0;iN;i){intr,theta;cinrtheta;byRadius[r].push_back(theta);}intE;cinE;while(E--){intH,A;cinHA;intWA1;// 角度窗口包含的整数角度个数intans0;// 枚举内半径 hfor(inth0;hR;h){intcnt[360]{0};// 当前半径区间内各角度出现次数// 半径区间 [h, hH) 且不超过 R-1intmaxRmin(R-1,hH-1);for(intrh;rmaxR;r){for(inttheta:byRadius[r]){cnt[theta];}}// 在环形角度上求长度为 W 的窗口最大和if(W360){// 覆盖所有角度直接求和inttotal0;for(inti0;i360;i)totalcnt[i];ansmax(ans,total);}else{// 复制数组便于处理环形intdoubled[720];for(inti0;i360;i){doubled[i]cnt[i];doubled[i360]cnt[i];}// 初始窗口 [0, W-1]intcur0;for(inti0;iW;i)curdoubled[i];intmaxWincur;// 滑动窗口起始角度从 1 到 359for(intstart1;start360;start){curcur-doubled[start-1]doubled[startW-1];if(curmaxWin)maxWincur;}ansmax(ans,maxWin);}}coutans\n;}}return0;}总结本题的关键在于将二维条件半径和角度分解为独立的两步优化。由于RRR很小直接枚举内半径hhh是高效的。角度维度上的环形窗口最大值问题通过复制数组和滑动窗口在O(360)O(360)O(360)时间内解决。这种“先固定一维再对另一维做滑动窗口”的技巧在类似范围查询问题中十分常用。需要特别注意角度区间是闭区间因此窗口长度应为A1A1A1且要处理好环形取模。另外当A359A359A359时窗口覆盖整个圆需单独处理避免重复计数。实现时注意数组越界和数据类型即可。