## Monday, July 4, 2016

### [CareerCup] 7.5 A Line Cut Two Squares in Half 平均分割两个正方形的直线

http://www.cnblogs.com/grandyang/p/4774754.html
7.5 Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis

```class Point {
public:
double _x, _y;
Point(double x, double y): _x(x), _y(y) {};
};

class Line {
public:
Point _start, _end;
Line(Point start, Point end): _start(start), _end(end) {};
};

/*
(left, top)_________
|         |
|         | size
|_________|
(right, down)
*/
class Square {
public:
double _left, _top, _right, _down, _size;
Square(double left, double top, double right, double down, double size): _left(left), _top(top), _right(right), _down(down), _size(size) {};
Point middle() {
return Point((_left + _right) * 0.5, (_top + _down) * 0.5);
}
// Return the point whrere the line connecting mid1 and mid2 intercepts the edge of square 1.
Point extend(Point mid1, Point mid2, double size) {
double xdir = mid1._x < mid2._x ? -1 : 1;
double ydir = mid1._y < mid2._y ? -1 : 1;
if (mid1._x == mid2._x) return Point(mid1._x, mid1._y + ydir * size * 0.5);
double slope = (mid1._y - mid2._y) / (mid1._x - mid2._x);
double x1 = 0, y1 = 0;
if (fabs(slope) == 1) {
x1 = mid1._x + xdir * size * 0.5;
y1 = mid1._y + ydir * size * 0.5;
} else if (fabs(slope) < 1) {
x1 = mid1._x + xdir * size * 0.5;
y1 = slope * (x1 - mid1._x) + mid1._y;
} else {
y1 = mid1._y + ydir * size * 0.5;
x1 = (y1 - mid1._y) / slope + mid1._x;
}
return Point(x1, y1);
}
// Calculate the line that connecting two mids
Line cut(Square other) {
Point p1 = extend(middle(), other.middle(), _size);
Point p2 = extend(middle(), other.middle(), -1 * _size);
Point p3 = extend(other.middle(), middle(), other._size);
Point p4 = extend(other.middle(), middle(), -1 * other._size);
Point start = p1, end = p1;
vector<Point> points = {p2, p3, p4};
for (int i = 0;i < points.size(); ++i) {
if (points[i]._x < start._x || (points[i]._x == start._x && points[i]._y < start._y)) {
start = points[i];
} else if (points[i]._x > end._x || (points[i]._x == end._x && points[i]._y > end._y)) {
end = points[i];
}
}
return Line(start, end);
}
};```
https://github.com/shyal/cracking-the-coding-interview/blob/master/interviewQuestions.txt
Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis

public class Square {
public Point middle() {
return new Point((this.left +this.right)/ 2.0, (this.top+ this.bottom)/ 2.0);
}

/* Return the point where the line segment connecting midl and mid2 intercepts
* the edge of square 1. That is, draw a line from mid2 to midl, and continue it
* out until the edge of the square. */
public Point extend(Point midl, Point mid2, double s ize) {
/* Find what direction the line mid2 -> midl goes. */
double xdir = midl.x < mid2.x ? -1 : 1;
double ydir = midl.y < mid2.y ? -1 : 1;

/* If midl and mid2 have the s ame x value, then the slope calculation will
* throw a divide by 0 exception. So, we compute this specially. */
if (midl.x == mid2.x) {
return new Point(midl.x, midl.y + ydir * size/ 2.0);
}

double slope = (midl.y - mid2.y) / (midl.x - mid2.x);
double xl = 0;
double yl = 0;

/* Calculate slope using the equation (yl - y2) / (xl - x2).
* Note: if the slope is "steep" (>1) then the end of the line segment will
* hit size/ 2 units away from the middle on the y axis. If the slope is
* "shallow" ( <1) the end of the line segment will hit size / 2 units away
* from the middle on the x axis. */
if (Math.abs(slope) == 1) {
xl = midl.x + xdir * size/ 2.0;
yl = midl.y + ydir * size/ 2.0;
} else if (Math.abs(slope) < 1) {// shallow slope
xl = midl.x + xdir * size/ 2.0;
yl = slope * (xl - midl.x) + midl.y;
} else {// steep slope
yl = midl.y + ydir * size/ 2.0;
xl = (yl - midl.y) /slope + midl.x;
}
return new Point(xl, yl);
}

public Line cut(Square other) {
/* Calculate where a line between each middle would collide with the edges of
* the squares */
Point pl = extend(this.middle(), other.middle(), this.size);
Point p2 = extend(this.middle(), other.middle(), -1 * this.size);
Point p3 = extend(other.middle(), this.middle(), other.size);
Point p4 = extend(other.middle(), this.middle(), -1 * other.size);

/* Of above points, find start and end of lines. Start is farthest left (with
* top most as a tie breaker) and end is farthest right (with bottom most as
* a tie breaker. */
Point start = pl;
Point end= pl;
Point[] points = {p2, p3, p4};
for (int i= 0; i < points.length; i++) {
if (points[i].x < start.x //
(points[i].x == start.x && points[i].y < start.y)) {
start = points[i];
} else if (points[i].x > end.x //
(points[i].x == end.x && points[i].y > end.y)) {
end = points[i];
}
}

return new Line(start, end);
}
}