安装栅栏
问题描述
在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。
扫描线算法
问题分析
$(x,y)$是否$(x_1,y_1)$ $(x_2,y_2)$三点共线
$\frac{y_2-y} {x_2-x}$ = $\frac{y_2-y_1} {x_2-x_1}$
$(x,y)$是否在$(x_1,y_1)$ $(x_2,y_2)$线的左侧
$\frac{y_2-y} {x_2-x}$ < $\frac{y_2-y_1} {x_2-x_1}$
$(x,y)$是否在$(x_1,y_1)$ $(x_2,y_2)$线的右侧
$\frac{y_2-y} {x_2-x}$ > $\frac{y_2-y_1} {x_2-x_1}$
排序points，先按照y递增，然后按照x递增
先计算左侧边沿上的点，再计算右侧边沿上的点。
左侧扫描方法：
数组元素大于两个元素
判断当前点和左侧数组的最后两个点的共线情况，如果左侧数组的最后一个点在线的右侧，则将左侧数组的最后一个元素剔除
满足这两个条件就将数组的最后元素剔除
右侧扫描同理