How about sorting the set of points, { (xi, yi) } by the key x.
The first point (x_min, y1) and the last point (x_max, y2) should be the two most distant points.
If the slope of the line is positive, then y1 should be y_min; otherwise y1 should be y_max.
The first point (x_min, y1) and the last point (x_max, y2) should be the two most distant points.
If the slope of the line is positive, then y1 should be y_min; otherwise y1 should be y_max.