骨骼 MTV onsite跪经

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第四题边都是垂直水平的，说明你可以以区间形式保存各个上下边组成的pair。把所有横坐标sort一下，自己定义一个class，每个class里保存左右值和上下的值的list，存在treemap里key是横坐标start，找的时候floorkey一下，然后判断纵坐标在不在这个class的纵坐标list里面

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

xh_pku 发表于 2018-1-6 05:55
这个多边形可以是往内凹的吧？我感觉这样做有问题 有可能上面两个交点下面两个交点然后还是在外面

哦对就是算出所有焦点看奇偶。。但不对，所以我后来觉得按45度射一条斜线出去就能避免边重合这个问题。

感谢楼主分享～～～～～～

wangtjwork 发表于 2018-1-6 07:31
哦对就是算出所有焦点看奇偶。。但不对，所以我后来觉得按45度射一条斜线出去就能避免边重合这个问题。

可能需要先判断在不在边上，O(n)time，因为点在边上的话射线与边的交点为偶数。不在边上的话再45度射线求交点个数判断在不在内部，O(n)time。

第一题很难啊，而且还顺便考了leetcode 152???

polygon那个题leetcode上有相似题目，比这个难多了，问的是给你一堆点能不能组建一个凸多边形。就是向量的差乘，比如考虑当前边ab, 和可能的内部点x，用向量ab差乘ax，如果小于零（不记得是大于零还是小于零了），则x在ab的右边，扫描一遍所有边，x在每条边的右边则，x在这个多边形内部。至于点在边上，则是差乘等于0.

第一题悲剧，遇到就认栽了吧，谁写都困难。。。。