Bamboo之寻找小金刚

分析

可以抽象为许多连续线段，分别计数左拐和右拐的个数。考察叉积的基础应用。
假设ABC三点构成一个夹角∠ABC，B就是拐点，AC是辅助形成夹角。考虑线段AB和BC形成的向量

sin∠ABC= （AB * BC）/|AB|*|BC|

两个向量的叉乘除以它们的模
所以叉乘可以判断夹角是否大于180°从而确定转向。当然叉积是有方向的，可以自己选择哪条边在前，只要标准统一即可。每三个点组成一组，遍历，分别计数左拐数和右拐数。具体叉积相关操作可以看《算法导论》

注意

常见的一种陷阱是给出的数据范围明确在int范围内，但是计算过程中+-*/尤其是+-，是很可能导致数据暂时超出int范围的，所以建议用long long，或者计算时强制转化为long long
另外观察n的范围1<n，有一组只有两个点的边界情况，此时没有拐点

代码

const int maxx = 1e6 + 5; struct point{long long x, y; }p[maxx]; long long dir(point pi, point pj, point pk) {return (pk.x - pi.x)*(pj.y - pi.y) - (pj.x - pi.x)*(pk.y - pi.y); } int main() {int n, a;while (~scanf("%d%d", &n, &a)){for (int i = 0; i<n; i++){scanf("%lld %lld", &p[i].x, &p[i].y);}long long left = 0, right = 0;long long ans = a, temp;if (n<3)ans = a;else{for (int i = 2; i<n; i++){temp = dir(p[i - 2], p[i - 1], p[i]);//printf("i=%d,temp =%d\n",i,temp);if (temp<0){ left++; ans += left; }else if (temp>0){ right++; ans -= right; }}}printf("%lld\n", ans);} }

转载于:https://www.cnblogs.com/AlvinZH/p/8185347.html

总结

以上是生活随笔为你收集整理的2016级算法第六次上机-A.Bamboo之寻找小金刚的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。