昨晚ABC442E题解
2026-01-25 12:12:11
发布于：上海
15阅读
0回复
0点赞
请结合这篇题解一起食用
题意解析：
给定一个平面直角坐标系和 个点 ，第 个点的坐标
有 次查询，每次给出两个点的编号 ，有一条射线从原点出发，初始时指向编号为 的点，绕原点顺时针旋转，直到恰好指向编号为 的点停止
在整个旋转过程中（包括初始和最终时刻），只要射线朝向某个方向，处在该方向上的所有点都会被瞬间“击中”。求旋转过程中，总共会被击中的点的数量
特殊情况
不同的点可以位于从原点出发的同一方向（即共线）。在这种情况下，它们会被视为同时被击中。
如果点 和 位于从原点出发的同一方向，则射线无需旋转，只击中该方向上的所有点。
数据范围：
预处理部分：
对每个怪物坐标 ，使用三角函数（对边:邻边）
atan2l(y[i],x[i]);
计算其相对于原点 (0,0) 的极角（弧度）。使用 long double 保证精度。
为了方便后续查询，将 输出的 范围统一调整到 ，随后按照极角排序(arctan)，利用unordered_map建立原本节点编号和排序后节点的映射关系
查询部分：
先根据unordered_map查找起始节点与结束节点的图上位置
因为我没有构造环形数组，因此分为两种情况:
起始节点的比结束节点的大（需跨越数组边界），则查询结果为在数组中大于等于起始节点的的数量加上小于等于结束节点的的数量
起始节点的比结束节点的小或相等（无需跨越数组边界），则查询结果为在数组中大于等于起始节点的的数量减去大于结束节点的的数量
最终代码：
#include<bits/stdc++.h>
using namespace std;
int n,q;
long double s[200005];
unordered_map<int,int>mp;
struct node
{
int id;
long double ang;
}a[200005];
bool cmp(node x,node y)
{
return x.ang<y.ang;
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
long double x,y;
cin>>x>>y;
a[i].ang=atan2l(y,x);//计算弧度
if(a[i].ang<0)a[i].ang+=2*M_PIl;//调整弧度，方便处理
a[i].id=i;//存储原编号
}
sort(a+1,a+n+1,cmp);//按弧度排序
for(int i=1;i<=n;i++)
{
mp[a[i].id]=i;//建立映射关系
s[i]=a[i].ang;//不想手搓二分查找，搞个数组方便lower_bound与upper_bound（Doge）
}
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
l=mp[l],r=mp[r];//查找图上位置 ,分类讨论
if(a[l].ang<a[r].ang)cout<<upper_bound(s****+n+1,a[l].ang)-s+n-(lower_bound(s****+n+1,a[r].ang)-s)<<endl;
else cout<<(upper_bound(s****+n+1,a[l].ang)-s)-(lower_bound(s****+n+1,a[r].ang)-s)<<endl;
}
return 0;
}
时间复杂度：
空间复杂度：
有帮助，赞一个