Bisect Squares: 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.
Hints: #468, #479, #528, #560
解法
1
2
3
4
5
6
7
8
9
10
11
|
^
│ ┌──────┐
│ │ │
│ │ │
│ └──────┘
│
│ ┌────┐
│ │ │
│ └────┘
│
└─────────────────────────────────────>
|
如上图，画一根线能够让两个正方形都被等分地一切为二。
先看如何把一个正方形等分地一切为二，当然是从它的中心开始切啦，只要一条线经过正方形的中心，那么肯定等分的把正方形一切为二。
那么把两个正方形一切为二就是把两个正方形的中心点连接起来，得到的延长线就行啦。
问题变成了两个子问题：
- 如何求得正方形中心点
- 如何给定两个点，求得线条的几何公式
代码：
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
|
public class Point {
private int x;
private int y;
}
public class Square {
private Point leftTop;
private int size;
public Point getCenterPoint() {
return new Point(leftTop.x + size / 2, leftTop.y - size / 2);
}
}
public class Line {
private double slope;
private double c;
}
public class VerticalLine {
private x;
}
public Line findLine(Square s1, Square s2) {
Point c1 = s1.getCenterPoint();
Point c2 = s2.getCenterPoint();
return makeLine(c1, c2);
}
private Line makeLine(Point p1, Point p2) {
if (p1.x == p2.x) {
// 垂直线
return new VerticalLine(p1.x);
}
double slope = (double)(p2.y - p1.y) / (p2.x - p1.x);
double c = p2.y - slope * p2.x;
return new Line(slope, c);
}
|
评论