问答

当前位置

Facebook面试题 | 凸多边形

  • Ta: 刘助教

题目描述

给定一个包含多边形顶点的List,List内的点按顺序排列(顺时针或逆时针),判断这个多边形是否是凸多边形(凸多边形的定义:如果把一个多边形的所有边中,有一条边向两方无限延长成为一直线时,其他各边都在此直线的同旁,那么这个多边形就叫做凸多边形。
Convex polygon

注:
1.点的个数在3到10000之间。
2.坐标范围[-10000,10000]。
3.你可以假设这个多边形是一个简单多边形,换句话说,我们确保在每个顶点上恰好有两条边相交,并且边彼此不会相交。

样例

Example 1:
输入:[[0,0],[0,1],[1,1],[1,0]]
输出:True
样例解释

Example 2:
输入:[[0,0],[0,10],[10,10],[10,0],[5,5]]
输出:False
样例解释

解题思路

a. 这题是一题几何题,给定一系列的点判断是否是凸多边形,根据凸多边形的定义,我们很容易就可以想到判断所有的点是不是在任意一条边的同旁即可,这么做的时间复杂度是O(n^2),对于这题的数据范围来说很低效。

b. 由于这题给出的多边形是一个简单多边形,因此我们不需要考虑边互相交叉的情况,所以我们可以直接判断这个多边形的每一个内角大小,若均小于(本题中可以等于)180度,则为凸多边形。

c. 判断两条边的夹角我们可以用向量的叉积来计算,二维向量A与向量B的叉积可以表示为|A×B|=AxBy-AyBx,若这个值大于0,则说明B指向A逆时针旋转0到180的方向,若这个值小于0,则说明B指向A顺时针旋转0到180的方向,若等于0,则两向量共线 。根据向量的叉积我们就可以判断这个多边形的内角是否均小于180度,相邻两条边的向量均保持顺时针或逆时针旋转才符合条件。

d.需要注意的是,我们需要额外判断一下(n-1,n)×(n,0)和(n,0)×(0,1)这两个叉积。并且叉积为0(即相邻的边共线,但不包括所有点共线)在本题中是可以被接受的。

参考程序

面试官角度分析

本题是一道平面几何题,需要了解一些几何的知识,难点是把向量的方向判断转化为叉积运算。同时需要考虑corner case(叉积为0,最后几条边的判断)。本题是中等偏简单难度的题,正确完成程序并处理好corner case可达到hire的评价。

题目答案链接

Convex Polygon 参考代码

相关题目

Max Points On A Line

0 个回复

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1