【题目描述】 给出平面上一些点(少于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 【提示】 直接穷举即可。
时间: 2023-05-29 13:01:40 浏览: 149
算法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编写的解答:
```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个整数点。 你的任务是找出这些点可以形成多少不同的正多边形。 输入描述 输入文件由几个测试样例组成。 每种情况下,第一行是数字N(N <= 500)。 接下来的N行,每行包含两个数字Xi和Yi(-100 <= xi,yi <= 100),表示点的位置(数据保证没有两个相同的位置的点)。 输出描述 对于每种情况,输出数字意味着这些点可以产生多少个不同的正多边形。c++编程实现该问题。
以下是C++代码实现:
```cpp
#include <iostream>
#include <map>
#include <cmath>
using namespace std;
int main() {
int n;
while (cin >> n) {
if (n <= 2) {
cout << "0" << endl;
continue;
}
int x[n], y[n];
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
map<pair<int, int>, int> pointMap;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dx = x[j] - x[i];
int dy = y[j] - y[i];
int gcd = __gcd(dx, dy);
dx /= gcd;
dy /= gcd;
int cnt = 2;
pair<int, int> p1 = make_pair(x[i] + dx, y[i] + dy);
pair<int, int> p2 = make_pair(x[j] + dx, y[j] + dy);
if (pointMap.count(p1)) {
cnt += pointMap[p1];
}
if (pointMap.count(p2)) {
cnt += pointMap[p2];
}
pointMap[p2] = pointMap[p1] + 1;
ans += cnt - 2;
}
pointMap.clear();
}
cout << ans << endl;
}
return 0;
}
```
具体思路:
1.输入点的坐标,存储到两个数组中。
2.确定两个点,计算它们之间的距离,以及两个点的中心点坐标。
3.使用map存储每个中心点的坐标以及出现的次数。
4.计算正多边形的数量。
5.最后清空map,继续下一组数据的处理。
时间复杂度为O(n^2*logn),空间复杂度为O(n^2)。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)