AtCoder ABC442_E: E - Laser Takahashi Editorial

557 字

3 分钟

AtCoder ABC442_E: E - Laser Takahashi Editorial

2026-01-31

次阅读

算法

AtCoder

/

算法

题目链接#

https://atcoder.jp/contests/abc442/tasks/abc442_e

题目大意#

问题描述#

在二维平面上有 $N$ 个怪兽，第 $i$ 个怪兽的坐标为 $(X_i, Y_i)$ （坐标不为原点）。高桥位于原点 $(0,0)$ 。他的眼睛会发射强力激光，能瞬间消灭当前面朝方向射线上的所有怪兽。

询问#

青木进行了 $Q$ 次独立的思想实验。对于第 $j$ 次实验，给定两个怪兽编号 $A_j$ 和 $B_j$ ：

初始时，高桥面朝怪兽 $A_j$ 的方向。
高桥开始顺时针旋转身体。
当他面朝怪兽 $B_j$ 的方向时，立即停止旋转。

目标： 计算在整个旋转过程中（包含起始方向和结束方向），总共有多少个怪兽被消灭。

注意事项#

如果在某一方向上存在多个怪兽，它们会被同时消灭。
如果怪兽 $A_j$ 和 $B_j$ 相对于原点在同一方向上，高桥不会旋转，仅消灭该方向上的怪兽。
$N, Q \le 2 \times 10^5$ ，坐标范围 $\pm 10^9$ 。

解题思路#

本题本质是环形区间的区间求和。

极角排序 (转化) 将二维坐标转化为一维的顺时针顺序。
- 方法：将平面按顺时针划分为 8 个区域（轴+象限），区域内利用叉积判断先后。
离散化分组 (去重) 排序后，同一射线上的怪兽会相邻。将它们合并为同一个 group_id，记录该组的怪兽数量 cnt。
前缀和 (查询) 对 cnt 数组做前缀和。
- 若 $A \to B$ 未跨越起跑线：sum[v] - sum[u-1]。
- 若跨越起跑线（转了一圈）：(sum[Total] - sum[u-1]) + sum[v]。

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N=2e5+10;
4
int n, q;
5
struct point{
6
  int idx, quadrant, groupid;
7
  long long x, y;
8
}a[N];
9
int idgroup[N], groupcnt[N], sum[N];
10
int u, v;
11
long long cross(point a, point b){
12
  return a.x*b.y-a.y*b.x;
13
}
14
bool cmp(point a, point b){
15
  if(a.quadrant!=b.quadrant) return a.quadrant<b.quadrant;
16
  long long cp=cross(a, b);
17
  return cp<0;
18
}
19
int main(){
20
  scanf("%d%d", &n, &q);
21
  for(int i=1;i<=n;i++) {
22
    scanf("%lld%lld", &a[i].x, &a[i].y);
23
    a[i].idx=i;
24
    if(a[i].x==0&&a[i].y>0) a[i].quadrant=0;//象限
25
    if(a[i].x>0&&a[i].y>0) a[i].quadrant=1;
26
    if(a[i].x>0&&a[i].y==0) a[i].quadrant=2;
27
    if(a[i].x>0&&a[i].y<0) a[i].quadrant=3;
28
    if(a[i].x==0&&a[i].y<0) a[i].quadrant=4;
29
    if(a[i].x<0&&a[i].y<0) a[i].quadrant=5;
30
    if(a[i].x<0&&a[i].y==0) a[i].quadrant=6;
31
    if(a[i].x<0&&a[i].y>0) a[i].quadrant=7;
32
  }
33
  sort(a+1, a+n+1, cmp);
34
  int m=0;
35
  for(int i=1;i<=n;i++) {
36
    if(i==1||a[i].quadrant!=a[i-1].quadrant||cross(a[i], a[i-1])!=0){
37
      m++;
38
      groupcnt[m]=0;
39
    }
40
    a[i].groupid=m;
41
    idgroup[a[i].idx]=m;
42
    groupcnt[m]++;
43
  }
44
  for(int i=1;i<=m;i++) sum[i]=sum[i-1]+groupcnt[i];
45
  while(q--){
46
    scanf("%d%d", &u, &v);
47
    int startg=idgroup[u];
48
    int endg=idgroup[v];
49
    if(startg==endg) printf("%d\n", groupcnt[startg]);
50
    else{
51
      int ans=0;
52
      if(startg<endg){
53
        ans=sum[endg]-sum[startg-1];
54
      }
55
      else {
56
        ans+=sum[m]-sum[startg-1];
57
                ans+=sum[endg];
58
      }
59
      printf("%d\n", ans);
60
    }
61
  }
62
  return 0;
63
}