思路

  其实是一个比较简单的最大不相交区间数量问题，因为所有圆的圆心都在同一条线上，那么每一个圆的左右与坐标轴相交的地方就是左右端点，将圆看作一个区间，所有圆不相交不重合就是所有的区间都相互分离，那么问题就是在许多的区间中选出一部分区间使得选出的区间不相交并使选出的区间数量最大，这其实一个经典的问题，只需要按照区间右端点进行排序，然后从左至右进行贪心的选取即可，具体证明可以自行了解

代码

python

# leetcode 435. 无重叠区间
n = int(input())
lines = []
for _ in range(n):
    x , y = map(int, input().split())
    left = x - y
    right = x + y
    lines.append((left, right))
lines.sort(key=lambda x: x[1])
ans = 0
now = -10**9
for left, right in lines:
    if left > now:
        ans += 1
        now = right
print(ans)

java

import java.util.Arrays;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] lines = new int[n][2];

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int left = x - y;
            int right = x + y;
            lines[i][0] = left;
            lines[i][1] = right;
        }

        // 排序
        Arrays.sort(lines, (a, b) -> Integer.compare(a[1], b[1]));

        int ans = 0;
        int now = -1000000000;

        for (int[] line : lines) {
            int left = line[0];
            int right = line[1];
            if (left > now) {
                ans += 1;
                now = right;
            }
        }

        System.out.println(ans);
    }
}

c++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> lines(n, vector<int>(2));

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        int left = x - y;
        int right = x + y;
        lines[i][0] = left;
        lines[i][1] = right;
    }

    sort(lines.begin(), lines.end(), [](const vector<int> &a, const vector<int> &b) {
        return a[1] < b[1];
    });

    int ans = 0;
    int now = -1000000000;

    for (const vector<int> &line : lines) {
        int left = line[0];
        int right = line[1];
        if (left > now) {
            ans += 1;
            now = right;
        }
    }

    cout << ans << endl;

    return 0;
}

题目内容

小美想要有一维坐标系$x$轴上画上尽可能多的圆，但是这些圆的位置不能存在相交、相切、内含这三种情况

小明给了$n$个圆心的位置和对应的半径，显然地，这些圆之间位置关系不一定会满足上面的情况，因此小美想通过删除一些圆来使得自己能够画尽可能多的圆。

小美想知道自己最多能画的圆的个数，你能帮帮她吗？

输入描述

第一行输入一个整数 $n$（$1≤n≤10^5$）代表点的个数。

接下来$n$对整数$x,y$($1≤x,y≤10^6$)分别表示圆心的位置($0,x$)和对应的半径。

输出描述

输出一个整数，表示小美最多能画的圆的个数

样例1

输入

5
11 1
2 1
5 1
14 1
8 1

输出

5

说明

所有的点画出来的圆的位置关系均满足不相交、不相切、不内含

样例2

输入

4
2 1
3 4
5 1
8 1

输出

3

说明

删除第二个点，能画三个满足条件的圆