有N条线段,可以是水平的,也可以是垂直的。现在我需要找出每条线段的交点总数和交点总数。N可以达到100000。我试着检查每一对线。答案是正确的,但我需要减少它所花费的时间。
这是我的代码:
using namespace std;
typedef struct Point
{
long long int x;
long long int y;
} ;
bool fun(Point p0, Point p1, Point p2, Point p3)
{
double s1_x, s1_y, s2_x, s2_y;
s1_x = p1.x - p0.x; s1_y = p1.y - p0.y;
s2_x = p3.x - p2.x; s2_y = p3.y - p2.y;
double s, t;
s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y + s1_x * s2_y);
t = ( s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x)) / (-s2_x * s1_y + s1_x * s2_y);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
return 1; // Collision detected
}
return 0; // No collision
}
int main()
{
long long int n // number of line segments;
Point p[n],q[n]; // to store end points of line segments
for( long long int i=0;i<n;i++)
{
// line segments is defined by 2 points P(x1,y1) and Q(x2,y2)
p[i].x=x1;
p[i].y=y1;
q[i].x=x2;
q[i].y=y2;
}
for( long long int i=0;i<n-1;i++)
{
for( long long int j=i+1;j<n;j++)
{
if(fun(p[i],q[i],p[j],q[j]))
count++;
}
}
return 0;
}
有人可以帮我降低这个程序的时间复杂度吗?