【题目描述】 给出平面上一些点(少于50个），坐标都是整数(|xi|,|yi| <= 109)，有可能重复。问存在多少个以这些点为顶点的平行于坐标轴的不同矩形。(两个矩形如果四个顶点坐标都相同，就算相同的矩形) 【输入】 第一行一个整数T(T <= 100)表示测试数据的组数 对于每组数据 第一行一个整数n，表示点的数量 下面n行每行两个整数xi,yi表示点的坐标。 【输出】 T行，每行一个整数表示以这些点为顶点的平行于坐标轴的矩形个数。 【输入样例】 1 7 0 0 0 1 0 2 1 0 1 1 1 2 0 0 【输出样例】 3 【提示】 直接穷举即可。

算法1

(暴力枚举) $O(n^4)$

枚举每个矩形的对角线顶点，并检查对角线上是否有点即可。

时间复杂度

暴力枚举每个矩形的对角线顶点，时间复杂度 $O(n^4)$。

C++ 代码

算法2

(次暴力枚举) $O(n^3)$

枚举每个矩形左上角和右下角的点，检查另外两个点是否存在即可。为了方便查找，可以将所有点放到一个 set 中。

时间复杂度

由于用了 set，查找时间复杂度 $O(\log n)$，故总时间复杂度为 $O(n^3 \log n)$。

C++ 代码

算法3

(暴力枚举+离散化) $O(n^3)$

还是枚举每个矩形左上角和右下角的点，检查另外两个点是否存在。为了方便检查，可以对所有点的坐标进行离散化，把点的坐标从 $[-10^9, 10^9]$ 映射到 $[0, n]$，使得坐标差距不是特别大，可以通过数组朴素方式来访问并保存。

时间复杂度

由于对坐标进行了离散化，故查找时间复杂度近似为 $O(1)$，故总时间复杂度为 $O(n^3)$。

C++ 代码

算法4

(暴力枚举+map) $O(n^3 \log n)$

还是枚举每个矩形左上角和右下角的点，检查另外两个点是否存在。为了方便查找，可以把所有点放到一个 map 中，以点坐标为 key，以点出现的次数为 value。

时间复杂度

由于用了 map，查找时间复杂度 $O(\log n)$，故总时间复杂度为 $O(n^3 \log n)$。

C++ 代码

相关问题

请用java写出以下题目 给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ，并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。 请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。 题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。

以下是使用Java编写的解答：

public class Solution {
    public int findMaxValue(int[][] points, int k) {
        int maxSum = Integer.MIN_VALUE;
        int left = 0;
        int right = 0;
        
        while (right < points.length) {
            while (points[right][0] - points[left][0] > k) {
                left++;
            }
            
            int sum = points[right][1] + points[left][1] + Math.abs(points[right][0] - points[left][0]);
            maxSum = Math.max(maxSum, sum);
            
            right++;
        }
        
        return maxSum;
    }
}

使用该解决方案，你可以通过调用 `findMaxValue` 方法并传入数组 `points` 和整数 `k` 来找到符合条件的最大值。注意，该方法假设输入的 `points` 数组已经按照横坐标 `x` 的值从小到大排序。

第一行是一个正整数数n（1<=n<=100），表示有n个炸弹 接下来n行有三个正整数，分别为xi，yi和ri。(0 <= xi, yi<= 105,1 <= ri <= 105) 前两个数表示第i个炸弹的中心坐标，ri表示该炸弹的爆炸半径。 写一个C++ 代码

这是一个关于处理二维空间内炸弹位置及其影响范围的问题，通常需要创建一个数据结构来存储每个炸弹的信息，并编写算法来检查某个点是否会被某个或所有炸弹的爆炸范围覆盖。这里是一个基本的C++代码示例：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Bomb {
    int x;
    int y;
    int r;
};

bool isAffected(int x, int y, const vector<Bomb>& bombs) {
    for (const Bomb& bomb : bombs) {
        double dist = sqrt((x - bomb.x) * (x - bomb.x) + (y - bomb.y) * (y - bomb.y));
        if (dist <= bomb.r) return true; // 如果距离小于等于半径，则受影响
    }
    return false;
}

int main() {
    int n;
    cin >> n;

    vector<Bomb> bombs(n);
    for (int i = 0; i < n; ++i) {
        cin >> bombs[i].x >> bombs[i].y >> bombs[i].r;
    }

    int queryX, queryY;
    cin >> queryX >> queryY;

    bool affected = isAffected(queryX, queryY, bombs);

    if (affected)
        cout << "爆破区域" << endl;
    else
        cout << "未受影响" << endl;

    return 0;
}

在这个代码中，首先读入炸弹的数量`n`和每个炸弹的详细信息。然后从输入中获取查询点的坐标，最后使用`isAffected`函数检查这个点是否位于任何一个炸弹的爆炸范围内。