Erect the fence是个典型的凸包问题。。狗这是要往ACM的方向杀过去了么。。

转专业的表示好想死 == 顺便来一发 我看到的还不错的凸包问题解释...
https://segmentfault.com/a/1190000000488339


[size=14.6667px]这题如果我被面到.... 那我也就随缘了
[size=14.6667px]

[size=14.6667px]今天解决了拓扑排序的利扣和林口的题。。 我要不要也打个卡呢

2011051305 发表于 2017-8-13 03:42
您好 请问cg的缩写是？ 是前面版上前辈提到的“计算几何”吗？ 谢谢！

是的，computational geometry。这个学科基本是个半死不活的学科。创立的很晚，但迅速得到了很多大神的兴趣，投入研究，结果瞬间把所有问题都解决的差不多了。。。没什么深度的学科。
面试按我理解，最基本的一个算法是左测试（判断一个点是否在一个向量左边）是个必须掌握的点，这个能用到N多种场合。比如判断是否是凸多边形啊，算凸包啊，都用。
其它的还有一些简单算法，比如判断一个点是否在多边形内，一个点是否能"看到“一个线段。其它的基本可以肯定不会考到了。

凸包不是ACM题。你写写试一试，基本是Medium里实现略麻烦级别的而已，如果知道凸包算法，它连LC hard都算不上。计算几何里基础算法而已。

貌似普林斯顿的算法I提到过凸包

因为bar越来越高了

这道题 我问一个 高中生 他秒答.....

凸包问题学过就是easy，没学过让你无中生有想这个，真让你想到解法那我建议直接去读个PhD吧

fentoyal 发表于 2017-8-13 01:23
凸包不是ACM题。你写写试一试，基本是Medium里实现略麻烦级别的而已，如果知道凸包算法，它连LC hard都算不 ...

好的前辈！

我今天仔细琢磨一下看能不能把这个题过了（但说实话 第一眼看上去这道题一点思路都没有 还是看了网上题解才意识到的 == 这大概就是成长的过程嘤嘤嘤嘤~~）

cg的知识点还是要补充的 临时想很困难

2011051305 发表于 2017-8-13 03:02
好的前辈！

我今天仔细琢磨一下看能不能把这个题过了（但说实话 第一眼看上去这道题一点思路都没有  ...

哈，我都没意识到lz原来是你，你的这个ID一串数字，太难认了。

fentoyal 发表于 2017-8-13 03:19
哈，我都没意识到lz原来是你，你的这个ID一串数字，太难认了。

被前辈认出来了 以后不敢在版上造次