题解

题目分析

题目描述了一个无限大的棋盘，棋盘上有 $n$ 个炮，每个炮的坐标是 $(x_i, y_i)$。每个炮的攻击方式如下：

• 选择一个攻击方向（上、下、左、右）。
• 该方向上看到的第一个棋子为“炮架”。
• 通过炮架攻击到炮架后面的棋子（只能攻击到炮架后面的第一个）。

我们的任务是求出每个炮第一次攻击能攻击到多少个炮。

解题思路

1. 坐标处理：我们需要对每个炮的坐标进行处理，分别统计每个 $x$ 坐标对应的 $y$ 坐标集合，以及每个 $y$ 坐标对应的 $x$ 坐标集合。

2. 排序：为了快速查找炮架后面的棋子，我们需要对每个 $x$ 坐标对应的 $y$ 坐标集合进行排序，以及对每个 $y$ 坐标对应的 $x$ 坐标集合进行排序。

3. 查找炮架后面的棋子：对于每个炮，我们分别在四个方向上查找炮架后面的棋子。这里有两种方法，第一种是使用二分查找来确定当前位置，第二种是直接判断前两个坐标和后两个坐标的炮是不是当前的炮。某一侧有两个及以上的炮，就能发动攻击。

4. 统计结果：对于每个炮，我们统计其在四个方向上能攻击到的炮的数量，并输出结果。

代码实现

Python 代码

import sys 
import bisect 
from collections import defaultdict 
 
def main():
    n = int(sys.stdin.readline())  # 读取点的数量 
    mp0 = defaultdict(list)  # 存储每个x对应的y列表 
    mp1 = defaultdict(list)  # 存储每个y对应的x列表 
    p = []  # 存储所有点的坐标 
    for _ in range(n):
        x, y = map(int, sys.stdin.readline().split())  # 读取每个点的x和y 
        mp0[x].append(y)  # 将y添加到x对应的列表中 
        mp1[y].append(x)  # 将x添加到y对应的列表中 
        p.append((x, y))  # 将点坐标添加到列表中 
    for x in mp0:
        mp0[x].sort()  # 对每个x对应的y列表进行排序 
    for y in mp1:
        mp1[y].sort()  # 对每个y对应的x列表进行排序 
    for i in range(n):
        cnt = 0  # 计数器，统计满足条件的点 
        x, y = p[i]  # 获取当前点的坐标 
        if x in mp0:
            k = bisect.bisect_left(mp0[x], y)  # 查找y在x对应的y列表中的位置 
            if k < len(mp0[x]) - 2:  # 如果y后面至少有两个点 
                cnt += 1 
            if k > 1:  # 如果y前面至少有两个点 
                cnt += 1 
        if y in mp1:
            k = bisect.bisect_left(mp1[y], x)  # 查找x在y对应的x列表中的位置 
            if k < len(mp1[y]) - 2:  # 如果x后面至少有两个点 
                cnt += 1 
            if k > 1:  # 如果x前面至少有两个点 
                cnt += 1 
        print(cnt)  # 输出当前点的计数器值 
 
if __name__ == "__main__":
    main()

C++ 代码

#include<bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;  // 读取点的数量 
    map<int, vector<int>> mp0, mp1;  // mp0存储每个x对应的y列表，mp1存储每个y对应的x列表 
    vector<array<int, 2>> p;  // 存储所有点的坐标 
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;  // 读取每个点的x和y 
        mp0[x].push_back(y);  // 将y添加到x对应的列表中 
        mp1[y].push_back(x);  // 将x添加到y对应的列表中 
        p.push_back({x, y});  // 将点坐标添加到列表中 
    }
    for (auto &[x, y] : mp0) {
        if (!y.empty()) {
            sort(y.begin(), y.end());  // 对每个x对应的y列表进行排序 
        }
    }
    for (auto &[x, y] : mp1) {
        if (!y.empty()) {
            sort(y.begin(), y.end());  // 对每个y对应的x列表进行排序 
        }
    }
    for (int i = 0; i < n; i++) {
        int cnt = 0;  // 计数器，统计满足条件的点 
        int x = p[i][0], y = p[i][1];  // 获取当前点的坐标 
        if (!mp0[x].empty()) {
            int k = lower_bound(mp0[x].begin(), mp0[x].end(), y) - mp0[x].begin();  // 查找y在x对应的y列表中的位置 
            if (k < ((int)mp0[x].size() - 2)) {  // 如果y后面至少有两个点 
                cnt++;
            }
            if (k > 1) {  // 如果y前面至少有两个点 
                cnt++;
            }
        }
        if (!mp1[y].empty()) {
            int k = lower_bound(mp1[y].begin(), mp1[y].end(), x) - mp1[y].begin();  // 查找x在y对应的x列表中的位置 
            if (k < ((int)mp1[y].size() - 2)) {  // 如果x后面至少有两个点 
                cnt++;
            }
            if (k > 1) {  // 如果x前面至少有两个点 
                cnt++;
            }
        }
        cout << cnt << endl;  // 输出当前点的计数器值 
    }
    return 0;
}

Java 代码

import java.util.*; 
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); 
        int n = sc.nextInt();   // 读取点的数量 
        Map<Integer, List<Integer>> xMap = new HashMap<>();  // 存储每个x对应的y列表 
        Map<Integer, List<Integer>> yMap = new HashMap<>();  // 存储每个y对应的x列表 
        List<int[]> p = new ArrayList<>();  // 存储所有点的坐标 
 
        // 读取并存储所有点的坐标 
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();   // 读取每个点的x 
            int y = sc.nextInt();   // 读取每个点的y 
            xMap.putIfAbsent(x,  new ArrayList<>());  // 初始化x对应的y列表 
            yMap.putIfAbsent(y,  new ArrayList<>());  // 初始化y对应的x列表 
            xMap.get(x).add(y);   // 将y添加到x对应的列表中 
            yMap.get(y).add(x);   // 将x添加到y对应的列表中 
            p.add(new  int[]{x, y});  // 将点坐标添加到列表中 
        }
 
        // 对每个x对应的y列表进行排序 
        for (List<Integer> list : xMap.values())  {
            Collections.sort(list); 
        }
 
        // 对每个y对应的x列表进行排序 
        for (List<Integer> list : yMap.values())  {
            Collections.sort(list); 
        }
 
        // 遍历每个点，统计满足条件的炮架后面的棋子 
        for (int i = 0; i < n; i++) {
            int cnt = 0;  // 计数器，统计满足条件的点 
            int x = p.get(i)[0],  y = p.get(i)[1];   // 获取当前点的坐标 
 
            // 检查上/下方向 
            List<Integer> xList = xMap.get(x); 
            if (xList != null) {
                if (xList.size()  >= 3) {  // 至少有三个点 
                    if (xList.get(0)  != y && xList.get(1)  != y) {  // 前两个点都不等于当前y 
                        cnt++;
                    }
                    if (xList.get(xList.size()  - 1) != y && xList.get(xList.size()  - 2) != y) {  // 后两个点都不等于当前y 
                        cnt++;
                    }
                }
            }
 
            // 检查左/右方向 
            List<Integer> yList = yMap.get(y); 
            if (yList != null) {
                if (yList.size()  >= 3) {  // 至少有三个点 
                    if (yList.get(0)  != x && yList.get(1)  != x) {  // 前两个点都不等于当前x 
                        cnt++;
                    }
                    if (yList.get(yList.size()  - 1) != x && yList.get(yList.size()  - 2) != x) {  // 后两个点都不等于当前x 
                        cnt++;
                    }
                }
            }
 
            System.out.println(cnt);   // 输出当前点的计数器值 
        }
    }
}

题目内容

在无限大的棋盘中有 $n$ 个炮，第 $i$ 个炮的坐标是$(x_i,y_i)$。

已知每个炮的攻击方式是:先选一个攻击方向(上、下、左、右)，该方向上看见的第一个棋子为“炮架”，该炮可以通过炮架攻击到炮架后面的棋子(只能攻击到炮架后面的第一个)

小美希望你求出每个炮第一次攻击能攻击到多少个炮。

输入描述

第一行输入一个正整数 $n$ ，代表炮的数量。

接下来的 $n$ 行，每行输入两个整数 $x_i,y_i$ ，代表每个炮所在的坐标。

$1 ≤ n ≤ 10^5$

$-10^5≤x_i,y_i ≤ 10^9$

输出描述

输出 $n$ 行，每行输出一个整数，代表第 $i$ 个炮可以攻击到的炮的数量。

样例1

输入

6
0 0
0 1
0 2
1 0
2 0
3 0

输出

2
0
1
1
1
1