leetcode【毎日1題】面接問題16.03.交点Java
24487 ワード
問題を解く
2つの線分(始点start={X 1,Y 1}と終点end={X 2,Y 2}として表される)が与えられ、それらに交点がある場合はその交点を計算し、交点がない場合は空の値を返します.
要求浮動小数点型誤差は10^-6を超えない.複数の交点(線分が重なる)があればX値が最も小さい点、X座標が同じであればY値が最も小さい点を返します.
ヒント:
座標の絶対値が2^7を超えない座標は有効な2 D座標です
の意見を打診
この問題は公式の問題解を直接参考するのは難しい.
トランスファゲート
Javaコード
コード搬送ゲート
2つの線分(始点start={X 1,Y 1}と終点end={X 2,Y 2}として表される)が与えられ、それらに交点がある場合はその交点を計算し、交点がない場合は空の値を返します.
要求浮動小数点型誤差は10^-6を超えない.複数の交点(線分が重なる)があればX値が最も小さい点、X座標が同じであればY値が最も小さい点を返します.
1:
:
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1}
: {0.5, 0}
2:
:
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
: {1, 1}
3:
:
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
: {},
ヒント:
座標の絶対値が2^7を超えない座標は有効な2 D座標です
の意見を打診
この問題は公式の問題解を直接参考するのは難しい.
トランスファゲート
Javaコード
class Solution {
public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
int x1 = start1[0], y1 = start1[1];
int x2 = end1[0], y2 = end1[1];
int x3 = start2[0], y3 = start2[1];
int x4 = end2[0], y4 = end2[1];
double[] ans = new double[2];
Arrays.fill(ans, Double.MAX_VALUE);
//
if ((y4-y3)*(x2-x1) == (y2-y1)*(x4-x3)) {
//
if ((y2-y1)*(x3-x1) == (y3-y1)*(x2-x1)) {
// (x3, y3) 「 」(x1, y1)~(x2, y2)
if (isInside(x1, y1, x2, y2, x3, y3)) {
updateRes(ans, x3, y3);
}
// (x4, y4) 「 」(x1, y1)~(x2, y2)
if (isInside(x1, y1, x2, y2, x4, y4)) {
updateRes(ans, (double)x4, (double)y4);
}
// (x1, y1) 「 」(x3, y3)~(x4, y4)
if (isInside(x3, y3, x4, y4, x1, y1)) {
updateRes(ans, (double)x1, (double)y1);
}
// (x2, y2) 「 」(x3, y3)~(x4, y4)
if (isInside(x3, y3, x4, y4, x2, y2)) {
updateRes(ans, (double)x2, (double)y2);
}
}
} else {
// t1 t2
double t1 = (double)(x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1));
double t2 = (double)(x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3));
// t1 t2 [0, 1]
if (t1 >= 0.0 && t1 <= 1.0 && t2 >= 0.0 && t2 <= 1.0) {
ans[0] = x1 + t1 * (x2 - x1);
ans[1] = y1 + t1 * (y2 - y1);
}
}
if (ans[0] == Double.MAX_VALUE) {
return new double[0];
}
return ans;
}
// (x, y) 「 」(x1, y1)~(x2, y2)
// (x, y) 「 」(x1, y1)~(x2, y2)
private boolean isInside(int x1, int y1, int x2, int y2, int x, int y) {
// x , x
// y , y
// ,
return (x1 == x2 || (Math.min(x1, x2) <= x && x <= Math.max(x1, x2)))
&& (y1 == y2 || (Math.min(y1, y2) <= y && y <= Math.max(y1, y2)));
}
private void updateRes(double[] ans, double x, double y) {
if (x < ans[0] || (x == ans[0] && y < ans[1])) {
ans[0] = x;
ans[1] = y;
}
}
}
コード搬送ゲート