企业官网建设流程全解析

题目描述

Radars Inc.\texttt{Radars Inc.}Radars Inc.是一家世界知名的雷达制造商，其卓越声誉源于严格的质量保证流程以及适合各种预算的多种雷达型号。公司雇佣你来开发一项详细的检测程序，该程序由一系列EEE个实验组成，针对某一特定监视型号。

检测区域用极坐标平面表示，平面上有NNN个物体，位于整数极坐标位置。被检测的雷达模型位于原点(0,0)(0,0)(0,0)，能够探测距离小于其探测范围RRR的物体，扫描区域由四个调节参数α\alphaα、AAA、hhh、HHH定义。

形式化地，雷达的扫描区域为极坐标点集合：

{(r,θ)∣h≤r<h+H, α≤θ≤α+A} \{(r,\theta)\mid h \le r < h+H,\; \alpha \le \theta \le \alpha+A\}{(r,θ)∣h≤r<h+H,α≤θ≤α+A}

其中α,A,h,H\alpha, A, h, Hα,A,h,H均为整数：

• α\alphaα：扫描起始角度，0≤α<3600 \le \alpha < 3600≤α<360；
• AAA：扫描开角，0≤A<3600 \le A < 3600≤A<360；
• hhh：内半径，0≤h<R0 \le h < R0≤h<R；
• HHH：径向厚度，1≤H≤R1 \le H \le R1≤H≤R。

物体(r,θ)(r,\theta)(r,θ)会被雷达显示当且仅当h≤r<h+Hh \le r < h+Hh≤r<h+H且α≤θ≤α+A\alpha \le \theta \le \alpha+Aα≤θ≤α+A，其中角度不等式按模360∘360^\circ360∘理解（即在圆周上比较角度）。

给定平面上NNN个物体，你需要通过EEE个特定参数设置的实验来检测雷达模型。每个实验中，参数HHH和AAA固定，而α\alphaα（0≤α<3600 \le \alpha < 3600≤α<360）和hhh（0≤h<R0 \le h < R0≤h<R）可以自由选择为整数，要求计算出雷达最多能显示多少个物体。

输入格式

输入包含多个测试用例。每个测试用例描述如下：

• 第一行两个整数NNN和RRR，分别表示物体数量和探测范围（1≤N≤1041 \le N \le 10^41≤N≤104，2≤R≤1022 \le R \le 10^22≤R≤102）。
• 接下来NNN行，每行两个整数rir_iri​和θi\theta_iθi​，表示第iii个物体的极坐标（1≤ri<R1 \le r_i < R1≤ri​<R，0≤θi<3600 \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​≤R，0≤Aj<3600 \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≤r<h+Hh \le r < h+Hh≤r<h+H和角度条件α≤θ≤α+A\alpha \le \theta \le \alpha+Aα≤θ≤α+A（模360∘360^\circ360∘）。注意到hhh和α\alphaα的选择是相互独立的，因此我们可以枚举所有可能的hhh，然后在每个hhh下，只考虑半径满足条件的物体，再在角度维度上求一个长度为A+1A+1A+1的连续环形区间内的最大物体数。最终答案即为所有hhh下该最大值中的最大者。

由于RRR最大只有100100100，而角度范围固定为360360360，因此枚举所有hhh并逐区间统计是完全可行的。每个实验的复杂度约为O(R⋅(N+360))O(R \cdot (N + 360))O(R⋅(N+360))，在给定限制下可以轻松通过。

解题思路

数据预处理

对于每个测试用例，我们将物体按半径分组存储。因为R≤100R \le 100R≤100，可以创建一个大小为RRR的数组，每个元素是一个列表，存放该半径上所有物体的角度值。这样在枚举hhh时，可以快速获取半径落在[h,h+H)[h, h+H)[h,h+H)内的所有物体。

枚举内半径hhh

对于每个可能的hhh（0≤h<R0 \le h < R0≤h<R），执行以下步骤：

1. 清空一个长度为360360360的计数数组cnt\textit{cnt}cnt，cnt[θ]\textit{cnt}[\theta]cnt[θ]表示当前半径区间内角度为θ\thetaθ的物体个数。
2. 遍历半径rrr从hhh到min⁡(R−1,h+H−1)\min(R-1, h+H-1)min(R−1,h+H−1)，将该半径上所有物体的角度累加到cnt\textit{cnt}cnt中。
3. 现在问题转化为：在环形数组cnt[0…359]\textit{cnt}[0 \ldots 359]cnt[0…359]上，寻找一个长度为W=A+1W = A+1W=A+1的连续区间（因为角度包含两端，所以区间包含的整数角度数为A+1A+1A+1），使得区间内元素和最大。

环形窗口最大值

为了处理环形，我们将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×100=10610^4 \times 100 = 10^6104×100=106）。
• 滑动窗口计算为O(360)O(360)O(360)。
• 单次实验复杂度O(R⋅N+R⋅360)O(R \cdot N + R \cdot 360)O(R⋅N+R⋅360)，总实验数E≤100E \le 100E≤100，最坏总复杂度约100×(106+3.6×104)≈108100 \times (10^6 + 3.6 \times 10^4) \approx 10^8100×(106+3.6×104)≈108，在222秒内可行（实际常数很小）。

代码实现

// Inspecting Radars// UVa ID: 12323// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.260s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN,R;while(cin>>N>>R){if(N==0&&R==0)break;// 按半径分组存储每个物体角度vector<vector<int>>byRadius(R);// 半径 0 ~ R-1，实际物体半径 >=1for(inti=0;i<N;++i){intr,theta;cin>>r>>theta;byRadius[r].push_back(theta);}intE;cin>>E;while(E--){intH,A;cin>>H>>A;intW=A+1;// 角度窗口包含的整数角度个数intans=0;// 枚举内半径 hfor(inth=0;h<R;++h){intcnt[360]={0};// 当前半径区间内各角度出现次数// 半径区间 [h, h+H) 且不超过 R-1intmaxR=min(R-1,h+H-1);for(intr=h;r<=maxR;++r){for(inttheta:byRadius[r]){cnt[theta]++;}}// 在环形角度上求长度为 W 的窗口最大和if(W>=360){// 覆盖所有角度，直接求和inttotal=0;for(inti=0;i<360;++i)total+=cnt[i];ans=max(ans,total);}else{// 复制数组便于处理环形intdoubled[720];for(inti=0;i<360;++i){doubled[i]=cnt[i];doubled[i+360]=cnt[i];}// 初始窗口 [0, W-1]intcur=0;for(inti=0;i<W;++i)cur+=doubled[i];intmaxWin=cur;// 滑动窗口，起始角度从 1 到 359for(intstart=1;start<360;++start){cur=cur-doubled[start-1]+doubled[start+W-1];if(cur>maxWin)maxWin=cur;}ans=max(ans,maxWin);}}cout<<ans<<'\n';}}return0;}

总结

本题的关键在于将二维条件（半径和角度）分解为独立的两步优化。由于RRR很小，直接枚举内半径hhh是高效的。角度维度上的环形窗口最大值问题通过复制数组和滑动窗口在O(360)O(360)O(360)时间内解决。这种“先固定一维，再对另一维做滑动窗口”的技巧在类似范围查询问题中十分常用。

需要特别注意角度区间是闭区间，因此窗口长度应为A+1A+1A+1，且要处理好环形取模。另外，当A=359A=359A=359时窗口覆盖整个圆，需单独处理避免重复计数。实现时注意数组越界和数据类型即可。