CareerCup

Assuming that 'unique' refers to line slopes. That being said, store the Slope of every possible line in a Set and check the set before returning 2 points as a line. O(n^2) complexity and O(n^2) memory.

EDIT: Forgot in original version to account for the offset in the line equation (the c in y = mx + c). That's now accounted for. Thanks Boris

class Point{
    double x, y;
}

class Line {
    double m, c;

    Line(double m, double c){
        this.m = m;
        this.c = c;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + getOuterType().hashCode();
        long temp;
        temp = Double.doubleToLongBits(c);
        result = prime * result + (int) (temp ^ (temp >>> 32));
        temp = Double.doubleToLongBits(m);
        result = prime * result + (int) (temp ^ (temp >>> 32));
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Point other = (Point) obj;
        if (!getOuterType().equals(other.getOuterType()))
            return false;
        if (Double.doubleToLongBits(c) != Double.doubleToLongBits(other.c))
            return false;
        if (Double.doubleToLongBits(m) != Double.doubleToLongBits(other.m))
            return false;
        return true;
    }
}

public static Collection<Point[]> getLines(Point[] points){
    if(points == null){
        throw new NullPointerException();
    }

    ArrayList<Point[]> results = new ArrayList<Point[]>();
    HashSet<Line> lineCache = new HashSet<Line>();
    for(int i = 0; i < points.length; i++){
        Point p1 = points[i];
        for(int j = i + 1; j < points.length; j++){
            Point p2 = points[j];
            double slope = (p1.x - p2.x);
            double c;
            if(slope == 0){
                slope = Double.POSITIVE_INFINITY;
                c = Double.POSITIVE_INFINITY;
            }
            else{
                slope = (p1.y - p2.y) / slope;
                c = p1.y - slope * p1.x;
            }
            Line line = new Line(slope, c);
            if(!lineCache .contains(line)){
                lineCache .add(line);
                Point[] segment= new Point[2];
                line[0] = p1;
                line[1] = p2;
                results.add(segment);
            }
        }
    }
    return results;
}

Hey !

Line means slope and offset or you have the equation ax + by + c = 0.
So:
1. It should be a Map to enalbe you to save the offset for each slope in hashMap.
2. If the line is veritcal so slope in INF, and you get a problem, so either use another DS for special lines or check this special cases (x1 == x2) || (y1 == y2) and use some MAX_DOUBLE or something to indicate INF.

This breaks on:

1. Vertical lines. You'll be dividing by zero!
2. Hashing floating points. Double(0.00001).hashCode() != Double(0.0000100001).hashCode()

import java.util.*;

public class UniqueLines {

    public static final double EPSILON = 0.0001;
    private static final String FORMAT = "%.4f";


    public static class Point {
        public final double x;
        public final double y;

        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public boolean isEquivalent(Point other) {
            return (Math.abs(other.x - x) < EPSILON) &&
                   (Math.abs(other.y - y) < EPSILON);
        }
    }


    public static class Line {
        public final double slope;      // in the case of vertical lines: POSITIVE_INFINITY
        public final double intercept;  // in the case of vertical lines: the X-intercept

        public Line(double slope, double intercept) {
            // normalize -0.0/0.0
            if (Math.abs(slope - 0.0) < EPSILON) {
                this.slope = 0.0;
            }
            else {
                this.slope = slope;
            }
            // normalize -0.0/0.0
            if (Math.abs(intercept - 0.0) < EPSILON) {
                this.intercept = 0.0;
            }
            else {
                this.intercept = intercept;
            }
        }

        @Override
        public boolean equals(Object other) {
            if (other instanceof Line) {
                Line otherLine = (Line) other;

                if (slope == Double.POSITIVE_INFINITY && otherLine.slope != Double.POSITIVE_INFINITY ||
                    otherLine.slope == Double.POSITIVE_INFINITY && slope != Double.POSITIVE_INFINITY) {
                    return false;
                }
                else if (slope == Double.POSITIVE_INFINITY && otherLine.slope == Double.POSITIVE_INFINITY) {
                    return String.format(FORMAT, intercept).equals(String.format(FORMAT, otherLine.intercept));
                }
                else {
                    return String.format(FORMAT, slope).equals(String.format(FORMAT, otherLine.slope)) &&
                           String.format(FORMAT, intercept).equals(String.format(FORMAT, otherLine.intercept));
                }
            }
            return false;
        }

        @Override
        public int hashCode() {
            if (slope == Double.POSITIVE_INFINITY) {
                return String.format(FORMAT, intercept).hashCode();
            }
            else {
                return String.format(FORMAT, slope).hashCode() |
                       String.format(FORMAT, intercept).hashCode();
            }
        }
    }


    public static int numberOfUniqueLines(Point[] points) {
        HashSet<Line> lines = new HashSet<Line>();
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                if (points[i].isEquivalent(points[j])) continue;

                double slope, intercept;

                // check for vertical line
                if (Math.abs((points[j].x - points[i].x)) < EPSILON) {
                    slope = Double.POSITIVE_INFINITY;
                    intercept = points[i].x;
                }
                else {
                    slope = (points[j].y - points[i].y) / (points[j].x - points[i].x);
                    intercept = points[i].y - slope * points[i].x;
                }

                Line line = new Line(slope, intercept);
                lines.add(line);
            }
        }

        return lines.size();
    }

}

Treat each point as a node in a graph and each node is connected to each other. For example, if we have 4 points, A, B, C, D then we have AB, AC, AD, BC, BD and CD. So we pick any node and do a DFS/BFS and each "step" is a line.

n(n-1)/2

#include<iostream>
#include<map>
#include<vector>
using namespace std;

void create_list(int (*points)[2], int n) {
	multimap<float,int *> map;
	for (int i = 0; i < 4; i++) {
		for (int j = i+1; j < 5; j++) {
			float slope = (float)(points[i][1] - points[j][1]) / (points[i][0] - points[j][0]);
			int *a = new int[2];
			a[0] = i;
			a[1] = j;
			map.insert(pair<float, int *>(slope, a));
		}
	}

	for (multimap<float, int *>::iterator iter = map.begin(); iter != map.end(); iter++) {
		cout << "slope=" << iter->first << " " << "points = {{" << points[iter->second[0]][0] << "," << points[iter->second[0]][1] <<
	"}, {" << points[iter->second[1]][0] << "," << points[iter->second[1]][1] << "}" << endl;
	}
}

int main(void) {
	int points[5][2] = { {1,2},
	{2,3},
	{3,4},
	{1,3},
	{2,5} };
	create_list(points, 5);
	getchar();
	return 1;

}