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

1

假设算法是正确的，我想：你在 32 位上运行并得到一个整数溢出。

于 2013-10-13T20:01:13.807 回答
0

您不应该在外围函数中的 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 回答