intersection-lcci

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。

英文版：Cracking the Coding Interview，源自硅谷程序员的面试红宝书

LCCI

Given two straight line segments (represented as a start point and an end point), compute the point of intersection, if any. If there&#39;s no intersection, return an empty array.
The absolute error should not exceed 10^-6. If there are more than one intersections, return the one with smallest X axis value. If there are more than one intersections that have same X axis value, return the one with smallest Y axis value.

Example 1: 

<pre>
Input: 
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1}
Output: {0.5, 0}
</pre>

Example 2: 

<pre>
Input: 
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
Output: {1, 1}
</pre>

Example 3: 

<pre>
Input: 
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
Output: {} (no intersection)
</pre>

Note: 

<ul>
	<li>The absolute value of coordinate value will not exceed 2^7.</li>
	<li>All coordinates are valid 2D coordinates.</li>
</ul>

intersection

Intersection LCCI

Geometry

Math

给定两条线段（表示为起点<code>start = {X1, Y1}</code>和终点<code>end = {X2, Y2}</code>），如果它们有交点，请计算其交点，没有交点则返回空值。

要求浮点型误差不超过<code>10^-6</code>。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。

&nbsp;

示例 1：

<pre>输入：
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1}
输出： {0.5, 0}
</pre>

示例 2：

<pre>输入：
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
输出： {1, 1}
</pre>

示例 3：

<pre>输入：
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
输出： {}，两条线段没有交点
</pre>

&nbsp;

提示：

<ul>
	<li>坐标绝对值不会超过 2^7</li>
	<li>输入的坐标均是有效的二维坐标</li>
</ul>