1

入力: ポイントのセット 出力: これらのポイントから作成された凸包の周囲

理由はわかりませんが、一部の入力でまだ境界が正しくありません (どの入力かわかりません)。私のアルゴリズムに何か問題があるかどうか教えてください。(または実装)

#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;
};
4

2 に答える 2

0

perimeter 関数の for ループの後に次のコードを追加しないでください。

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

凸包の最初の点と最後の点の間の距離を追加します。

于 2013-10-13T14:01:01.667 に答える