写C++程序,读入平面上的N个点,输出任一组4个或更多共线的点,以O(N^2logN)时间运行
时间: 2024-03-24 17:40:08 浏览: 16
好的,以下是一个C++程序,可以读入平面上的N个点,输出任一组4个或更多共线的点,并且以O(N^2logN)时间运行:
```c++
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> Point;
struct Line {
int a, b, c;
Line(Point p1, Point p2) {
a = p1.second - p2.second;
b = p2.first - p1.first;
c = p1.first * p2.second - p2.first * p1.second;
int gcd = __gcd(__gcd(a, b), c);
a /= gcd;
b /= gcd;
c /= gcd;
if (a < 0 || (a == 0 && b < 0)) {
a = -a;
b = -b;
c = -c;
}
}
bool operator<(const Line& rhs) const {
if (a != rhs.a) return a < rhs.a;
if (b != rhs.b) return b < rhs.b;
return c < rhs.c;
}
};
int main() {
int n;
cin >> n;
vector<Point> points(n);
for (int i = 0; i < n; i++) {
cin >> points[i].first >> points[i].second;
}
// 枚举所有点对,计算它们所在的直线,然后统计相同直线的点数
map<Line, vector<Point>> lines;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Line line(points[i], points[j]);
lines[line].push_back(points[i]);
lines[line].push_back(points[j]);
}
}
// 找到包含4个或更多点的直线,输出这些点
for (auto& p : lines) {
if (p.second.size() >= 4) {
cout << "共线的点:";
for (auto& point : p.second) {
cout << "(" << point.first << ", " << point.second << ") ";
}
cout << endl;
break;
}
}
return 0;
}
```
该算法的时间复杂度为O(N^2logN),其中,枚举所有点对的时间复杂度为O(N^2),每个点对计算所在直线的时间复杂度为O(logN),最后统计相同直线的点数的时间复杂度为O(N^2logN)。