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

ym3fd 发表于 2017-8-13 03:08
cg的知识点还是要补充的 临时想很困难

您好 请问cg的缩写是？ 是前面版上前辈提到的“计算几何”吗？ 谢谢！

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

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

凸包算法在算法导论里就有。。。。。

另外大家可能对ACM这三个字母看得太重了。

实际上ACM里面的水题可以很水，就和LC的hard差不多。

而LC的一些题目其实也都是从竞赛题目转化过来的，比如最初150题里面的那个maximum rectangle.

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

是的. 推荐邓俊辉老师的 计算几何

但是有人这题直接秒杀…