/** Store a polygon edge for the scan line algorithm */
class Edge {
    private int x1,y1; //end point with smallest y coord
    private int x2,y2; //end with largest y
    private float a,b; //line is x = a*y + b;

    Edge(int x1, int y1, int x2, int y2) {
	if(y2 == y1) { //horizontal line
	    a = 0.0f;  //to avoid dividing by 0
	    b = 0.0f;
	} else {
	    a = (x2-x1)/(float)(y2-y1);
	    b = x1 - a*y1;
	}
	if (y1 < y2) {
	    this.x1 = x1;
	    this.y1 = y1;
	    this.x2 = x2;
	    this.y2 = y2;
	} else {
	    this.x1 = x2;
	    this.y1 = y2;
	    this.x2 = x1;
	    this.y2 = y1;
	}
    }
  
    /* x coord on line given y */
    float xof(float y) {
	return a*y+b;
    }

    /* x coord on line given y rounded up to integer*/
    int xofi(int y) {
	return (int) Math.round(0.5+xof(y));
    }

    int miny() {
	return y1;
    }

    int maxy() {
	return y2;
    }

    /* Does ray going right from (x,y) intersect edge? */ 
    boolean rayIntersect(int x, int y) {
	if (y >= y2) return false;
	if (y < y1) return false;
	return xof(y) > x;
    }
	public String toString() {
	return "("+x1+","+y1+")-("+x2+","+y2+")";
    }

}