爲什麼我的凸包外圍計算不起作用？

我不知道爲什麼，但我仍然得到一些輸入（我不知道是哪個輸入）不良周邊製成凸包的周長。你能告訴我，如果有什麼不好我的alghorithm？後波紋管（或執行）

#include<iostream> 
#include<vector> 
#include<algorithm> 
#include<cmath> 
#include<iomanip> 
using namespace std; 


struct Point{ 
    int x; 
    int y; 

    bool operator<(const Point &p)const 
    { 
    return (x<p.x || (x==p.x && y<p.y)); 
    } 
}; 

long long cross(Point A, Point B, Point C) 
    { 
     return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x); 
    } 



vector<Point> ConvexHull(vector<Point> P) //Andrew's monotone chain 
    { 
    vector<Point> H; //hull 
    H.resize(2*P.size()); 

    int k=0; 

    if(P.size()<3) return H; 
    sort(P.begin(),P.end()); 

    //lower 
    for(int i=0;i<P.size();i++) 
    { 
     while(k>=2 && cross(H[k-2],H[k-1],P[i])<=0) 
      k--; 
     H[k]=P[i]; 
     k++;   
    } 

    int t=k+1; 

    //upper 
    for(int i=P.size()-2; i>=0 ;i--) 
    { 
     while(k>=t && cross(H[k-2],H[k-1],P[i])<=0) 
      k--; 
     H[k]=P[i]; 
     k++; 
    } 


    H.resize(k); 
    return H; 
}; 

double perimeter(vector<Point> P) 
{ 
    double r=0; 
    for(int i=1;i<P.size();i++) 
     r+=sqrt(pow(P[i].x-P[i-1].x,2)+pow(P[i].y-P[i-1].y,2)); 
    return r; 
} 


int main(){ 
     int N; 
     cin>>N; 
     vector<Point>P; 
     P.resize(N); 

     for(int i=0;i<N;i++) 
      cin>>P[i].x>>P[i].y; 

     vector<Point>H; 
     H=ConvexHull(P); 

     cout<<setprecision(9)<<perimeter(H)<<endl; 
     //system("pause"); 
     return 0; 
};

來源

2013-10-13 Serillan

你的代碼產生的點集有哪些特徵（a）正確的輸出和（b）錯誤的輸出？你從自己的努力中學到了什麼，可以診斷問題的根源呢？ –

其實它正在通過在線測試，所以我沒有看到輸入。我知道：點數≥3且1≤x，y≤10^6。（每個點的x和y） – Serillan

「凸包的最小周長」是什麼意思？對於一組給定的點，只有一個凸包，並且它只有一個邊界。 –

假設算法是正確的，我想象：你在32位運行，並得到一個整數溢出。

來源

2013-10-13 20:01:13

你不應該添加的代碼在周邊功能循環：

r += sqrt(pow(P[P.size() - 1].x-P[0].x,2)+pow(P[P.size() - 1].y-P[0].y,2));

您要添加的第一，並在最後一個點之間的距離凸包。

來源

2013-10-13 14:01:01 armin

船體數組中的最後一點與第一個點相同。 –

爲什麼我的凸包外圍計算不起作用？

回答

相關問題