這道題目是很標準的凸包問題，看了第五章開頭的說明，照著寫就好。 判斷向量夾角用交叉積，右手螺旋，注意交叉積不滿足交換率，所以要注意前后順序。

?

/* ID: zhangyc1 LANG: C++ TASK: fc */ #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std;struct SPoint {double x, y, theta; }; SPoint arrPoint[10000], centerPoint; int arrChosen[10000]; int N;int compare(const void* argv1, const void* argv2) {if (((SPoint*)argv1)->theta < ((SPoint*)argv2)->theta)return -1;else if (((SPoint*)argv1)->theta > ((SPoint*)argv2)->theta)return 1;else return 0; }inline bool IsAngleConvex(SPoint& P1, SPoint& Pc, SPoint& P3) {// Convex : (P3 - PC) X (P1 - PC) > 0 return (P3.x - Pc.x) * (P1.y - Pc.y) - (P3.y - Pc.y) * (P1.x - Pc.x) > 0; }void GiftWrapping() {// 選前兩個點arrChosen[0] = 0, arrChosen[1] = 1;int nIdx = 2, nCur = 1, nSt = 0;// 選中間節點while (nIdx < N){while (nCur > 0 && !IsAngleConvex(arrPoint[arrChosen[nCur - 1]], arrPoint[arrChosen[nCur]], arrPoint[nIdx]))nCur--;arrChosen[++nCur] = nIdx;nIdx++;}// 選最后一個節點while (1){// ncur-1, ncur, nst 不為凹if (nCur - nSt > 2 && !IsAngleConvex(arrPoint[arrChosen[nCur - 1]], arrPoint[arrChosen[nCur]], arrPoint[arrChosen[nSt]])){nCur--;continue;}// ncur, nst, nst+1 不為凹if (nCur - nSt > 2 && !IsAngleConvex(arrPoint[arrChosen[nCur]], arrPoint[arrChosen[nSt]], arrPoint[arrChosen[nSt + 1]]))nSt++;elsebreak;}// 計算周長double dbLen = sqrt((arrPoint[arrChosen[nSt]].x - arrPoint[arrChosen[nCur]].x) * (arrPoint[arrChosen[nSt]].x - arrPoint[arrChosen[nCur]].x) +(arrPoint[arrChosen[nSt]].y - arrPoint[arrChosen[nCur]].y) * (arrPoint[arrChosen[nSt]].y - arrPoint[arrChosen[nCur]].y));for (int i = nSt + 1; i <= nCur; i++){dbLen += sqrt((arrPoint[arrChosen[i]].x - arrPoint[arrChosen[i - 1]].x) * (arrPoint[arrChosen[i]].x - arrPoint[arrChosen[i - 1]].x) +(arrPoint[arrChosen[i]].y - arrPoint[arrChosen[i - 1]].y) * (arrPoint[arrChosen[i]].y - arrPoint[arrChosen[i - 1]].y));}printf("%.2lf\n", dbLen); }void prepairData() {scanf("%d", &N);centerPoint.x = centerPoint.y = 0.0;for (int i = 0; i < N; i++){scanf("%lf%lf", &arrPoint[i].x, &arrPoint[i].y);centerPoint.x += arrPoint[i].x;centerPoint.y += arrPoint[i].y;}centerPoint.x /= N;centerPoint.y /= N; }void process() {for (int i = 0; i < N; i++){arrPoint[i].theta = atan2(arrPoint[i].y - centerPoint.y, arrPoint[i].x - centerPoint.x);}qsort(arrPoint, N, sizeof(SPoint), compare);GiftWrapping(); }int main(){freopen("fc.in","r",stdin);freopen("fc.out","w",stdout);prepairData();process();return 0; }

?

?

轉載于:https://www.cnblogs.com/doublemystery/archive/2013/04/19/3030413.html

總結

以上是生活随笔為你收集整理的Fencing the Cows [USACO]的全部內容，希望文章能夠幫你解決所遇到的問題。

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