N 라인 교차점 찾기에 걸리는 시간 단축

Question

N 라인 세그먼트가 수평 또는 수직입니다. 이제 선분 당 총 교차점 수와 교차점 수를 알아야합니다. N은 까지 갈 수 있습니다. 모든 라인 쌍을 검사 해 보았습니다. 대답은 정확하지만 시간을 줄여야합니다.

이

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; 
} 

누군가가이 프로그램의 시간 복잡도를 감소 나를 도울 수 :

여기 내 코드입니까?

Answer 1

다음은 Fenwick 트리가있는 스윕 라인을 사용하는 O (n log n) 시간 알고리즘입니다.

단계 0 : 정렬

의 X 좌표를 매핑 좌표 등 순서를 유지하도록 0..N-1의 정수에 의해 각각의 값을 대체. y- 좌표도 똑같이하십시오. 교차 속성은 보존되며 알고리즘은 더 쉽게 구현할 수 있습니다.

1 단계 : 평행 한 선분

I 수평 세그먼트에 대해이 단계를 설명 할 것이다. 수직 세그먼트에 대해서도 반복하십시오.

가로 세그먼트를 y 좌표로 그룹화합니다. 한 번에 하나의 그룹을 처리하여 다음과 같이 스윕 라인에 대한 이벤트를 만듭니다. 각 세그먼트는 더 낮은 엔드 포인트에서 시작 이벤트를 가져오고 더 큰 엔드에서 중지 이벤트를 얻습니다. 닫힌 선분을 원한다면 정지 전에 정렬을 시작하십시오. 스윕 라인과 현재 교차하는 선 세그먼트 수 및 처리 된 시작 이벤트 수를 추적하여 정렬 된 순서로 이벤트를 스윕합니다. 세그먼트에 대한 병렬 교차 수는 (시작 시간에 교차 된 세그먼트 수 + 중지 시간에 처리 된 시작 이벤트 수 - 시작 시간에 처리 된 시작 이벤트 수)입니다. (이것에 대한 내 이전의 설명도 Given a set of intervals, find the interval which has the maximum number of intersections를 참조하십시오.)

2 단계 : 선분 수직

나는 각 수평 라인 세그먼트에 대한 계산의 측면에서이 단계를 설명 할 것이다 얼마나 많은 수직 선분 교차합니다.

우리는 또 다른 스윕 라인 알고리즘을 수행합니다. 이벤트는 수평 세그먼트 시작, 수직 세그먼트 및 수평 세그먼트 정지이며, 닫힌 선 세그먼트를 가정하여 순서대로 정렬됩니다. Fenwick 트리를 사용하여 각 y 좌표에 대해 얼마나 많은 수직 세그먼트가 지금까지 y 좌표를 포함했는지 추적합니다. 수평 시작을 처리하려면 교차 좌표에서 y 좌표에 대한 트리 값을 빼십시오. 수평 정지를 처리하려면 교차 좌표에 y 좌표의 트리 값을 추가하십시오. 이것은 카운트가 차이에 의해 증가 함을 의미하는데, 이는 활성 상태에서 수평 세그먼트를 찔렀다는 수직 세그먼트의 수입니다. 수직 세그먼트를 처리하려면 Fenwick 트리의 힘을 사용하여 더 낮은 y 좌표와 큰 값 (닫힌 세그먼트를 포함하여 포함) 사이의 모든 값을 빠르게 증가시킵니다.

원하는 경우 이러한 스윕 라인 알고리즘을 결합 할 수 있습니다. 나는 해설 적 이유로 그들을 분리시켰다.