时间戳

首页 > 解决方案 > 求 n 条线段与两条平行线上端点的交点数

algorithm - 求 n 条线段与两条平行线上端点的交点数

问题描述

求两条平行线上的端点与 n 条线段的交点数。

设两组 n 个点：

A={p1,p2,…,pn} on y=0 B={q1,q2,…,qn} on y=1 每个点 pi 与其对应的点 qi 相连形成一条线段。

观点

我需要使用分治算法编写代码，该算法返回所有 n 线段的交点数。

例如：

输入：

3
1 101
-234 234
567 765

输出：

1

我编码如下，但我有错误的答案。

任何人都可以帮助我使用此代码或为我提供另一个解决方案吗？

#include<iostream>
#include <vector>
#include<algorithm>

using namespace std;

    void merge1(vector< pair <int, int> > vect, int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;

        vector< pair <int, int> > vect_c_l(n1);
        vector< pair <int, int> > vect_c_r(n2);

        for (int i = 0; i < n1; i++)
            vect_c_l[i] = vect[l + i];
        for (int j = 0; j < n2; j++)
            vect_c_r[j] = vect[m + 1 + j];

        int i = 0;
        int j = 0;

        int k = l;
        
        while (i < n1 && j < n2) {
            if (vect_c_l[i].first <= vect_c_r[j].first) {
                vect[k] = vect_c_l[i];
                i++;
            }
            else {
                vect[k] = vect_c_r[j];
                j++;
            }
            k++;
        }

    
        while (i < n1) {
            vect[k] = vect_c_l[i];
            i++;
            k++;
        }

        while (j < n2) {
            vect[k] = vect_c_r[j];
            j++;
            k++;
        }
    }

    int merge2(vector< pair <int, int> > vect, int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;
        int inv_count = 0;
        vector< pair <int, int> > vect_c_l(n1);
        vector< pair <int, int> > vect_c_r(n2);

        for (int i = 0; i < n1; i++)
            vect_c_l[i] = vect[l + i];
        for (int j = 0; j < n2; j++)
            vect_c_r[j] = vect[m + 1 + j];

    
        int i = 0;
        int j = 0;

        int k = l;

        while (i < n1 && j < n2) {
            if (vect_c_l[i].second < vect_c_r[j].second) {
                vect[k] = vect_c_l[i];
                i++;
            }
            else {
                vect[k] = vect_c_r[j];
                j++;
                inv_count = inv_count + (m - i);

            }
            k++;
        }


        while (i < n1) {
            vect[k] = vect_c_l[i];
            i++;
            k++;
        }

        while (j < n2) {
            vect[k] = vect_c_r[j];
            j++;
            k++;
        }
        return inv_count;
    }

    void mergeSort1(vector< pair <int, int> > vect, int l, int r) {
        if (l >= r) {
            return;
        }
        int m = l + (r - l) / 2;
        mergeSort1(vect, l, m);
        mergeSort1(vect, m + 1, r);
        merge1(vect, l, m, r);
    }

    int mergeSort2(vector< pair <int, int> > vect, int l, int r) {
        int  inv_count = 0;
        if (r > l) {
            int m = l + (r - l) / 2;

            inv_count += mergeSort2(vect, l, m);
            inv_count += mergeSort2(vect, m+ 1, r);

            /*Merge the two parts*/
            inv_count += merge2(vect, l, m + 1, r);
        }
        return inv_count;
    
    }

int main() {
    int n,c=0;
    
    cin >> n;
    int a, b;
    vector< pair <int, int> > vect;

    for (int i = 0;i < n;i++) {
        cin >> a >> b;
        vect.push_back(make_pair(a, b));
    }
    mergeSort1(vect,0,n-1);

    cout << mergeSort2(vect,0, n - 1);
}

标签： algorithmlinedivide-and-conquer

解决方案

我会利用这样的想法，即计算线段是否相交比计算它们相交的位置要简单得多。如果两个线段的 x 值在 y=1 和 y=0 上位于彼此的不同侧，则它们相交。（即，如果一个段上的两个 x 值都小于其他值，或者都大于其他值）。

对象使这很容易陈述。构建一个段对象，其主要工作是确定它是否与另一个实例相交。

class Segment {
  constructor(x) {
    this.x0 = x[0];
    this.x1 = x[1];
  }
  // answer whether the reciever intersects the passed segment
  intersects(segment) {
    // this is ambiguous in the problem, but assume touching endpoints
    // count as intersections
    if (this.x0 === segment.x0 || this.x1 === segment.x1) return true;
    let sort0 = this.x0 < segment.x0
    let sort1 = this.x1 < segment.x1
    return sort0 !== sort1
  }
}

let input = [
  [1, 101],
  [-234, 234],
  [567, 765]
];
let segments = input.map(x => new Segment(x))

// check segments with one another in pairs
let pairs = segments.map((v, i) => segments.slice(i + 1).map(w => [v, w])).flat();
let intersections = pairs.reduce((acc, p) => p[0].intersects(p[1]) ? acc + 1 : acc, 0)
console.log(intersections)

推荐阅读