n条直线有多少个交点？

Question

问题是，通过给定x0,y0,x1,y1给定n行。获取集合点的数量。三条或更多条线相交是没有意义的。行通过 (x0, y0), (x1, y1)。不会有同一条线。我有一个想法是首先声明一个 HashMap，当一个新行到来时，得到它的斜率。如果 slop 值不在 HashMap 中，则结果 = 结果 + 我们现在有多少行。如果 slop 在 HashMap 中，则结果 = result +（我们现在有多少行 - 这个 slop 有多少行）。这是我的主要代码部分。

public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    int[][] lines = new int[in.nextInt()][4];
    Map<Double, Integer> map = new HashMap<>();
    int cross = 0;
    for(int i = 0; i< lines.length; i++){
        for(int j = 0; j< 4; j++)
            lines[i][j] = in.nextInt();
        double slop;
        if(lines[i][2] - lines[i][0] == 0)
            slop = Double.POSITIVE_INFINITY;
        else
            slop = (double)(lines[i][3] - lines[i][1]) / (lines[i][2] - lines[i][0]);
        if(!map.containsKey(slop)) {
            cross = cross + i;
            map.put(slop, 1);
        }else{
            cross = cross + (i - map.get(slop));
            map.put(slop, map.get(slop) + 1);
        }
    }
    System.out.print(cross + "\n");
}

但是测试结果显示是错误的。有人可以帮助我解决我没有注意到的情况或者我的代码有什么问题吗？

Answer 1

任何一对非平行线都会相交。

因此，交叉点的数量是唯一斜率数量的多项式函数。

直线的斜率给出为 Rise/Run，但直接使用此除法是危险的，因为在浮点数学中 4.2/2.2 和 8.4/4.4 可能不会给出相同的结果.同样，减去 x0-x1 可能会引入浮点怪异。

由于看起来您正在以整数形式读取坐标，因此请考虑将斜率存储为 (Rise,Run) 对。但是请注意 -Rise/Run 和 Rise/-Run 看起来不同；因此，约定如果斜率为负，则该符号应存储在 Rise 中。现在，简化你的分数，也许使用 GCD algorithm.

现在你有一个独特而精确的坡度（比以前好得多）。

现在，像以前一样进行：如果斜率是唯一的，那么斜率的数量会增加哈希集中已有条目的数量。

Answer 2

这是个不错的小问题。由于我们处理的是直线，并且我们知道同一条直线不会出现两次，并且我们知道相同的交点不会出现两次，所以解决方案 almost 一样简单每对线计算一个交点，即 n * (n-1) / 2。但是，这是假设每对线都有一个交点，如果任何线都是平行的，则不成立；所以我们需要计算每个斜率有多少条线共享相同的斜率。看来你已经想通了。

但是，从您的代码中并不清楚您是否正确使用了这些坡度计数来计算交叉点的数量。在你的循环中有一些加法和减法很难推理。如果分两个阶段执行，算法会更清晰。

如果有 r 条斜率相同的线，则 n * (n-1) / 2 公式假设它们会形成 r * (r-1) / 2 个交点，但由于这些线是平行的，它们实际上交点为 0它们之间的点。所以我们需要减去r * (r-1) / 2来修正计数。我们需要对每个坡度独立地执行此操作。

因此算法可以按如下方式工作：

构建斜率地图以进行计数。
将total初始化为n * (n-1) / 2，其中n是行数。
对于地图值中的每个计数 r，从总数中减去 r * (r-1) / 2。

这是一个实现：

import java.util.Map;
import java.util.HashMap;
import java.util.Scanner;

public class CountIntersections {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextInt();

        Map<Double, Integer> slopeCounts = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int x0 = in.nextInt(), y0 = in.nextInt(),
                x1 = in.nextInt(), y1 = in.nextInt();

            double slope;
            if(x0 == x1) {
                slope = Double.POSITIVE_INFINITY;
            } else {
                slope = (double) (y1 - y0) / (x1 - x0);
            }

            slopeCounts.put(slope, slopeCounts.getOrDefault(slope, 0) + 1);
        }

        long total = n * (n-1) / 2;
        for(long r : slopeCounts.values()) {
            total -= r * (r-1) / 2;
        }
        System.out.println(total);
    }
}

变量 n、total 和 r 被声明为类型 long 而不是 int 以便乘法 n * (n-1) 不't overflow。这是 n and/or r 的值大于约 46,000 的问题。

请注意，此处将斜率计算为 doubles 没有问题。从 Scanner 读取的数字是 ints，所有这些都可以精确表示为 doubles。减法将是精确的，the IEEE 754 specification guarantees that division of floating point numbers will be correctly rounded。因此数值不精确不会导致两个相等的斜率因浮点运算而计算出略有不同。

n条直线有多少个交点？

How many intersect points does n line have?

algorithm

graph-algorithm