题解：AT_abc442_e [ABC442E] Laser Takahashi

· · 题解

AT_abc442_e [ABC442E] Laser Takahashi 题解

题目大意

平面直角坐标系上有 N 个怪物，坐标 (X_i,Y_i)。原点处的高桥会发射激光，消灭他面对方向上的所有怪物。

有 Q 次询问：从面向怪物 A 开始顺时针旋转到面向怪物 B，求总共被消灭的怪物数（包括 A,B）。

如果 A,B 方向相同就不旋转。会同时消灭同一方向上的多个怪物。

思路

注意到 X 和 Y 的取值范围很大 (-10^9\leq X_i,Y_i \leq 10^9)，所以不能用 atan2 直接算角度，精度会炸，所以用象限 + 叉积的方法来比较方向。

核心：

查询：

设方向 A 排序后位置为 x，方向 B 排序后位置为 y：

时间复杂度：O(N\log N + Q)。

环形查询部分有点绕，画图秒懂： 

2(90°)
/      \
3(180°)  1(0°)
\      /
4(270°)

代码


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N(2e5+5);
int n,q;
int cnt[N],id[N],pre[N]; //cnt:每方向怪物数 id:怪物方向编号 pre:前缀和
map<pair<int,int>,vector<int>>mp; //方向->怪物列表
vector<pair<int,int>>dir; //全部方向向量
bool cmp(pair<int,int>a,pair<int,int>b){
    auto[x1,y1](a);
    auto[x2,y2](b);
    bool p(y1>0 or !y1 and x1>0); //a在上半平面或正x轴
    bool q(y2>0 or !y2 and x2>0); //b在上半平面或正x轴
    if(p!=q) return p>q; //上半平面排前
    else return x1*y2>x2*y1; //同半平面逆时针排序(叉积)
}
signed main(){
    cin>>n>>q;
    for(int i=1,x,y;i<=n;++i){
        cin>>x>>y;
        int g(__gcd(abs(x),abs(y))); //约分统一方向
        if(g) x/=g,y/=g;
        if(!mp[{x,y}].size()) dir.push_back({x,y}); //新方向进列表
        mp[{x,y}].push_back(i); //怪物加入方向组
    }
    sort(dir.begin(),dir.end(),cmp); //逆时针排方向
    for(int i=0;i<dir.size();++i){
        cnt[i+1]=mp[dir[i]].size(); //记方向怪物数
        for(int k:mp[dir[i]]) id[k]=i+1; //记怪物方向编号
    }
    for(int i=1;i<=dir.size();++i) pre[i]=pre[i-1]+cnt[i]; //前缀和
    for(int a,b;q--;){
        cin>>a>>b;
        int x(id[a]),y(id[b]); //怪物方向编号
        if(x==y) cout<<cnt[x]<<'\n'; //同方向即该方向所有怪物
        else if(x>y) cout<<pre[x]-pre[y-1]<<'\n'; //逆时针区间和
        else cout<<pre[dir.size()]+pre[x]-pre[y-1]<<'\n'; //顺时针绕一圈
    }
}