An answer to this question on Stack Overflow.

Question

The question is, given n lines by giving x0, y0, x1, y1. Get the number of meeting points. there will be no point that three or more lines intersect. Lines pass (x0, y0), (x1, y1). There will be no same line. I have an idea is first declare a HashMap, when a new line come, get its slop. If the slop value is not in the HashMap, the result = result + how many lines we have right now. If the slop is in the HashMap, the result = result + (how many lines we have right now - how many lines is with this slop). Here is my main part of code.

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

But the test results shows it is wrong. Could someone help me with which case that I didnt notice or is there anything wrong with my code.

Answer

Any pair of non-parallel lines will intersect.

Therefore, the number of intersections is a polynomial function of the number of unique slopes.

The slope of a line is given as Rise/Run, but it's dangerous to use this division directly since in floating-point mathematics 4.2/2.2 and 8.4/4.4 may not give the same result. Similarly, subtracting x0-x1 may introduce floating-point weirdness.

Since it looks as though you are reading the coordinates as integers, consider storing your slopes as (Rise,Run) pairs. But notice that -Rise/Run and Rise/-Run look different; therefore, make a convention that if a slope is negative, that sign should be stored in the Rise. Now, simplify your fraction, perhaps by using a GCD algorithm.

Now you have slope in a unique and exact form (much better than what you had before).

Now, proceed as before: if the slope is unique then the number of slopes increases by the number of entries already in your hashset.