一、題目

??給定兩條線段（表示為起點(diǎn) start = {X1, Y1} 和終點(diǎn) end = {X2, Y2}），如果它們有交點(diǎn)，請(qǐng)計(jì)算其交點(diǎn)，沒(méi)有交點(diǎn)則返回空值。

??要求浮點(diǎn)型誤差不超過(guò) 10^-6。若有多個(gè)交點(diǎn)（線段重疊）則返回 X 值最小的點(diǎn)，X 坐標(biāo)相同則返回 Y 值最小的點(diǎn)。

示例 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}
輸出： {}，兩條線段沒(méi)有交點(diǎn)

提示：

• 坐標(biāo)絕對(duì)值不會(huì)超過(guò) 2^7
• 輸入的坐標(biāo)均是有效的二維坐標(biāo)

??點(diǎn)擊此處跳轉(zhuǎn)題目。

二、C# 題解

??這題寫的心累，參考了 LeetCode 官方解法，代碼如下：

public class Solution {public double[] Intersection(int[] start1, int[] end1, int[] start2, int[] end2) {int       xa  = start1[0], xb = end1[0], xc = start2[0], xd = end2[0];int       ya  = start1[1], yb = end1[1], yc = start2[1], yd = end2[1];double[] ans = { };if ((xa - xb) * (yc - yd) != (ya - yb) * (xc - xd)) { // 不平行int    r = (xd - xc) * (yb - ya) - (yd - yc) * (xb - xa);int    p = (xc - xa) * (yd - yc) - (yc - ya) * (xd - xc);int    q = (xa - xc) * (yb - ya) - (ya - yc) * (xb - xa);double m = p * -1.0 / r, n = q * 1.0 / r;if (0 <= m && m <= 1 && 0 <= n && n <= 1) ans = new[] { xa + (xb - xa) * m, ya + (yb - ya) * m };}else if ((xa - xb) * (yc - ya) == (ya - yb) * (xc - xa)) { // 平行且在一條直線上Operation(xa, ya, xc, yc, xd, yd, ref ans);Operation(xb, yb, xc, yc, xd, yd, ref ans);Operation(xc, yc, xa, ya, xb, yb, ref ans);Operation(xd, yd, xa, ya, xb, yb, ref ans);}return ans;}private void Operation(int xp, int yp, int xa, int ya, int xb, int yb, ref double[] ans) {if (xp == xa && InLine(yp, ya, yb)) Update(xp, yp, ref ans);else if (xp != xa && InLine(xp, xa, xb)) Update(xp, yp, ref ans);}private bool InLine(int p, int a, int b) {return a <= p && p <= b || b <= p && p <= a;}private void Update(int x, int y, ref double[] ans) {if (ans.Length == 0) ans = new double[] { x, y };else if (Math.Abs(x - ans[0]) < 1e-6) ans[1] = y < ans[1] ? y : ans[1];else if (x < ans[0]) {ans[0] = x;ans[1] = y;}}
}

• 時(shí)間：124 ms，擊敗 66.67% 使用 C# 的用戶
• 內(nèi)存：41.04 MB，擊敗 100.00% 使用 C# 的用戶