# Max Points on a Line

## Something about line

- Two Distinct Point
- Two-point form

so a line should be like

```
Line { Point1, Point2 }
function check_on_line(l, p)
#check p on l using Two-point form
p1, p2 <- l
return (x - p1.x) * (p2.y - p1.y) == (y - p1.y) * (p2.x - p1.x)
```

## Loop invariant to find all `Line`

and their `point_count`

s

Init: Build a collection(`C`

) for `Line`

s and put first `Line`

with first two `Point`

into it.

- take a new
`Point`

p `point_count++`

to any`Line`

in`C`

with`p`

on it- if p is not on any
`Line`

in`C`

, create`Line`

s with`p`

and all former`Point`

s - put new
`Line`

s into`C`

```
foreach p in input
on_some_line = False
foreach l in C
if check_on_line(l, c)
l.point_count = l.point_count + 1
on_some_line = True
if not on_some_line
foreach _p in input before p
l = build new Line with _p and p
add l to C
```

### Newly Built Line's point_count

It is wrong that newly built `Line.point_count = 0`

. Because the new `Line l`

may cross some `Line`

in `C`

,
and the cross point may be the in the input points.

In that case, the new `Line`

should have its `point_count = count of former p on it`

.

Patched `not on_some_line`

block

```
if not on_some_line
foreach _p in input before p
l = build new Line with _p and p
l.point_count = count of point input before p on l
add l to C
```

## Finding max

Search `C`

to find the max count.

### Source code *Read on Github*

```
1 /**
2 * Definition for a point.
3 * class Point {
4 * int x;
5 * int y;
6 * Point() { x = 0; y = 0; }
7 * Point(int a, int b) { x = a; y = b; }
8 * }
9 */
10 public class Solution {
11
12 static class Line{
13
14 Point p1;
15 Point p2;
16
17 int pointCount;
18
19 Line(Point p1, Point p2){
20 this.p1 = p1;
21 this.p2 = p2;
22
23 this.pointCount = 2;
24 }
25
26 boolean on(int x, int y){
27 return (x - p1.x) * (p2.y - p1.y) == (y - p1.y) * (p2.x - p1.x);
28 }
29
30 boolean on(Point p){
31 return on(p.x, p.y);
32 }
33 }
34
35 public int maxPoints(Point[] points) {
36
37 if(points.length < 2) return points.length;
38
39 ArrayList<Line> lines = new ArrayList<Line>();
40
41 lines.add(new Line(points[0], points[1]));
42
43 for(int i = 2; i < points.length; i++){
44 boolean on = false;
45 for(Line line : lines){
46 if(line.on(points[i])){
47 line.pointCount++;
48 on = true;
49 }
50 }
51
52 if(!on){
53 for(int j = 0; j < i; j++){
54 Line l = new Line(points[j], points[i]);
55 lines.add(l);
56
57 for(int k = 0; k < i; k++){
58 if(j != k && l.on(points[k])){
59 l.pointCount++;
60 break;
61 }
62
63 }
64 }
65 }
66 }
67
68
69 int max = Integer.MIN_VALUE;
70
71 for(Line line : lines){
72 if(line.pointCount > max) max = line.pointCount;
73 }
74
75 return max;
76
77 }
78 }
```