C++:写一个程序,读入平面上的N个点,并输出任一组4个或更多共线的点,使它以O(N^2logN)时间运行
时间: 2023-11-27 19:53:40 浏览: 33
思路:
1. 枚举两个点 i 和 j,计算它们与其他点的斜率,将所有斜率按大小排序。
2. 遍历所有斜率,将相同斜率的点加入一个集合中,如果集合大小达到4,就输出这四个点。
时间复杂度分析:
1. 枚举两个点需要 O(N^2) 的时间复杂度。
2. 计算斜率和排序需要 O(NlogN) 的时间复杂度。
3. 对于每个斜率,最多有 N 个点加入集合,因此总时间复杂度为 O(N^2logN)。
代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
struct Point {
int x, y;
};
bool cmp(const Point& a, const Point& b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int main() {
int n;
cin >> n;
vector<Point> points(n);
for (int i = 0; i < n; i++) {
cin >> points[i].x >> points[i].y;
}
sort(points.begin(), points.end(), cmp);
set<pair<int, int>> slope_points;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
slope_points.clear();
slope_points.insert({points[i].x, points[i].y});
slope_points.insert({points[j].x, points[j].y});
for (int k = 0; k < n; k++) {
if (k == i || k == j) {
continue;
}
int dx2 = points[k].x - points[i].x;
int dy2 = points[k].y - points[i].y;
if (dx * dy2 == dx2 * dy) {
slope_points.insert({points[k].x, points[k].y});
}
}
if (slope_points.size() >= 4) {
cout << "Found collinear points: ";
for (const auto& p : slope_points) {
cout << "(" << p.first << "," << p.second << ") ";
}
cout << endl;
}
}
}
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)