How to represent a line in a unique formation.


  • 0
    E

    That is, for example, x + y + 1 = 0 and 2x + 2y + 2 = 0 is the same.
    Does it mean that you have to normalize every line to the unique formation, or there is some way to compute the unique formation conveniently? Otherwise it may cause additional cost to compute wheter two pairs of (a,b,c) represent a same line.


  • 4
    P

    if a is not zero, normalize (a, b, c) such that they are co-prime and a is positive

    if a is zero, normalize (b, c) such that b and c is co-prime and b is positive

    a and b cannot be both zero.


  • 0
    E

    so cool ! Foget to normalize a or b to positive will cause subtle bug that hard to find.


  • 0
    P

    How exactly do you find a,b,c coefficients?


  • 0
    Y
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    Y

    here is another method that you don't need to normalize (a,b,c). Normally use slope to differentiate 2 lines. Only when 2 lines have the same slope, you can calculate the a,b,c for the first line. then to demonstrate if the start point and the end point of the second line fit this equation ax+by+c=0; If ax+by+c!=0 that means they are different lines.

    class Line{
       double slope;
       MyPoint start;
       MyPoint end;
       int a,b,c;
       Line(MyPoint start,MyPoint end){
    	   this.start=start;
    	   this.end=end;
    	   int d=(start.x-end.x);
    	   if(d==0) slope=Integer.MAX_VALUE;
    	   else {
    		int e=(start.y-end.y);
    		slope= (double)e/d;
    	   }
    
    	   this.a=(end.y-start.y);//calculate a,b,c for this Line to see if 2 end points of other are in the line.
    	   this.b=(start.x-end.x);
    	   this.c=end.x*start.y-start.x*end.y;
        }
    
       @Override
       public int hashCode() {
    	return new Double(slope).hashCode();
       }
       @Override
       public boolean equals(Object obj) {
    	Line other = (Line) obj;
    	if (slope != other.slope)
    		return false;
    	else{
    		if(!inThisLine(other.start)) return false;
    		if(!inThisLine(other.end)) return false;
    		return true;
    	}
       }
       public boolean inThisLine(MyPoint p){
    	   if(a*p.x+b*p.y+c!=0) return false;
    	   else return true;
       }
    }
    

    the whole solution:

    public class Solution {
        public int maxPoints(Point[] points) {
    	    if(points==null||points.length==0) return 0;
    	    int result=1;
    	    HashMap<Line,HashSet<MyPoint>> lines=new HashMap<Line,HashSet<MyPoint>>();
    	    HashMap<MyPoint,Counter> uniquePoints=new HashMap<MyPoint,Counter>();
    	    HashMap<Line,Counter> lineCounters=new HashMap<Line,Counter>();
    
    	    for(int i=0;i<points.length;i++){
    	    	    MyPoint mypoint=new MyPoint(points[i].x,points[i].y);
    		    if(uniquePoints.containsKey(mypoint)){
    			    uniquePoints.get(mypoint).increase();
    		    }else{
    			    uniquePoints.put(mypoint,new Counter());
    			    uniquePoints.get(mypoint).increase();
    		    }
    	    }
    
    	    MyPoint[] mypoints=uniquePoints.keySet().toArray(new MyPoint[0]);//all points are unique
    	    for(int i=0;i<mypoints.length;i++){
    		    result=Math.max(result,uniquePoints.get(mypoints[i]).val());
    		    for(int j=i+1;j<mypoints.length;j++){
    			    Line line=new Line(mypoints[i],mypoints[j]);
    			    if(!lines.containsKey(line)) {
    			        lines.put(line,new HashSet<MyPoint>());
    			        lineCounters.put(line,new Counter());
    			    }
    			    if(!lines.get(line).contains(mypoints[i])){
    			        lines.get(line).add(mypoints[i]);
    			        lineCounters.get(line).increase(uniquePoints.get(mypoints[i]).val());
    			    }
    			    if(!lines.get(line).contains(mypoints[j])){
    			        lines.get(line).add(mypoints[j]);
    			        lineCounters.get(line).increase(uniquePoints.get(mypoints[j]).val());
    			    }
    			    result=Math.max(result,lineCounters.get(line).val());
    		    }
    	    }
    	    return result;
        }
    }
    
    class Line{
        double slope;
        MyPoint start;
        MyPoint end;
        int a,b,c;
        Line(MyPoint start,MyPoint end){
    	    this.start=start;
    	    this.end=end;
    	    int d=(start.x-end.x);
    	    if(d==0) slope=Integer.MAX_VALUE;
    	    else {
    		    int e=(start.y-end.y);
    		    slope= (double)e/d;
    	    }
    
    	    this.a=(end.y-start.y);//calculate a,b,c for this Line to see if 2 end points of other are in the line.
    	    this.b=(start.x-end.x);
    	    this.c=end.x*start.y-start.x*end.y;
        }
    
        @Override
        public int hashCode() {
    	    return new Double(slope).hashCode();
        }
        @Override
        public boolean equals(Object obj) {
    	    Line other = (Line) obj;
    	    if (slope != other.slope)
    		    return false;
    	    else{
    		    if(!inThisLine(other.start)) return false;
    		    if(!inThisLine(other.end)) return false;
    		    return true;
    	    }
        }
        public boolean inThisLine(MyPoint p){
    	    if(a*p.x+b*p.y+c!=0) return false;
    	    else return true;
        }
    }
    
    class MyPoint{
        int x;
        int y;
        public MyPoint(int x,int y) {
    	    this.x=x;
    	    this.y=y;
        }
        @Override
        public int hashCode() {
    	    return x+y;
        }
        @Override
        public boolean equals(Object obj) {
    	    MyPoint other = (MyPoint) obj;
    	    if (x != other.x)
    		    return false;
    	    if (y != other.y)
    		    return false;
    	    return true;
        }
    }
    
    class Counter{
        private int x;
        Counter(){
            this.x=0;
        }
    
        void increase(){
            x++;
        }
    
        void increase(int y){
            x+=y;
        }
    
        int val(){
            return x;
        }
    }
    

    Basic Idea: 1 .first eliminate all same points ,All same points become one MyPoint and store the numbers in HashMap<MyPoint,Counter> uniquePoints=new HashMap<MyPoint,Counter>(); 2. two lines are different when slope are different. when slope are same. calculate a,b,c for first line and to see if the 2 end points of second line fit ax+by+c==0 .


  • 0
    P

    Using double could be dangerous because it is related to precision.


  • 0
    Y

    Thanks for your comment!
    I have considered precision problem also. But it is not a issue in my solution. Because I only used slope as a hashcode of a line. But two lines having the same hashcode doesn't ensure that they are the same. They may be in the collision list of same hashcode. so they will be check if they are "equals" using the equals method. I also have posted the whole solution above.


  • 0
    P

    But is it possible that two slopes calculated from the same line is slightly different?


  • 0
    Y

    That is a good point. what you talk about is |AN/BN-A/B|==epsilon A,B,N are integers. Although it doesn't happen in the test cases, and instinctively i think it won't happen if A B N are integers . But I will search for related resources to see if i can figure it out. Thank you!


  • 0
    P

    I think there might be a problem simply because double might not hold a accurate AN or BN and you have to cast them to double before doing a floating point division


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.