c – 减少找到N线交叉点所需的时间

概述有N个线段,可以是水平线也可以是垂直线.现在我需要找出每个线段的交叉点总数和交叉点总数. N可以达到100000.我尝试检查每一对线.答案是正确的,但我需要减少它所花费的时间. 这是我的代码： using namespace std;typedef struct Point{ long long int x; long long int y;} ;bool fun 有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;}

有人可以帮我减少这个程序的时间复杂度吗？

解决方法 这是一个O(n log n)时间算法,它使用带有Fenwick树的扫描线.

第0步：协调重新映射

对x坐标进行排序,并将每个值替换为0..n-1中的整数,以便保留顺序.对y坐标执行相同的 *** 作.保留交集属性,同时允许下面的算法更容易实现.

第1步：平行线段

我将为水平段描述此步骤.重复垂直段.

按y坐标对水平线段进行分组.一次处理一个组,为扫描线创建事件,如下所示.每个段在其较小的端点处获得启动事件,在其较大的端点处获得停止事件.如果您想要关闭的线段,则在停止前开始排序.按排序顺序扫描事件,跟踪当前与扫描线相交的线段数以及处理的启动事件数.段的平行交叉点的数量是(在停止时间处理的开始事件的开始时间数处交叉的段的数量 – 在开始时间处理的开始事件的数量). (另请参阅Given a set of intervals,find the interval which has the maximum number of intersections以获取此前的解释.)

第2步：垂直线段

我将根据每个水平线段计算它相交的垂直线段数来描述这一步骤.

我们做另一种扫描线算法.事件是水平段开始,垂直段和水平段停止,按照该顺序排序,假设闭合线段.我们使用Fenwick树来跟踪每个y坐标到目前为止有多少垂直线段覆盖了y坐标.要处理水平开始,请从其交叉点计数中减去其y坐标的树值.要处理水平停止,请将其y坐标的树值添加到其交叉点计数.这意味着计数会增加差值,这是在活动时刺入水平线的垂直线段的数量.要处理垂直线段,请使用Fenwick树的功能快速递增其较小y坐标与其较大坐标(包括假设闭合线段)之间的所有值.

如果需要,可以组合这些扫描线算法.出于说明原因,我将它们分开.

总结

以上是内存溢出为你收集整理的c – 减少找到N线交叉点所需的时间全部内容，希望文章能够帮你解决c – 减少找到N线交叉点所需的时间所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。