FilesExpand file tree

 master

/

MaxPointsonaLine.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

66 lines (55 loc) · 1.74 KB

 master

/

MaxPointsonaLine.java

Copy path

Top

File metadata and controls

• Code
• Blame

66 lines (55 loc) · 1.74 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

import java.util.HashMap;

import shared.Point;

public class MaxPointsonaLine {

public int maxPoints(Point[] points) {

if (points.length<3)

return points.length;

//at least two points can form a line

int max = 2;

for(int i=0;i<points.length-1;i++){

HashMap<Float,Integer> hm = new HashMap<Float,Integer>();

int samerow= 1;

int curmax = 2;

int dup = 0;

for(int j=i+1;j<points.length;j++){

//y not the same

if(points[i].y != points[j].y){

//0.0+ to avoid -0.0 when all x are the same, but y have negative

float slop = 0.0f + (float)(points[i].x -points[j].x)/(points[i].y -points[j].y);

if(hm.containsKey(slop)){

hm.put(slop, hm.get(slop)+1);

//check if need update max.

if(hm.get(slop)>curmax)

curmax = hm.get(slop);

}else{

hm.put(slop, 2);

// if(hm.get(slop)>curmax)

// curmax = hm.get(slop);

}

}else{

//x and y are the same, add 1 to the duplicate count.

if(points[i].x == points[j].x){

dup++;

}else{

//y is the same , to avoid the divide 0 error. use samerow to calculate this case.

samerow++;

if(samerow>curmax)

curmax = samerow;

}

}

}

if(curmax+dup>max)

max = curmax+dup;

}

return max;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Point a = new Point(1,1);

Point b = new Point(1,1);

Point c = new Point(1,1);

Point[] points = {a,b,c};

MaxPointsonaLine so = new MaxPointsonaLine();

System.out.print(so.maxPoints(points));

}

}