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之寻找小金刚的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。