2

CLRSから凸包を見つけるためにGraham Scan Algorithmを読んでいました。凸包の CLRS で指定されたアルゴリズムは ::

ここに画像の説明を入力

この行を理解できません (アルゴリズムのステップ 2):

2 つ以上の点が p0 に対して同じ極角を持っている場合、そのような最も遠い点を除くすべての点は、p0 と最も遠い点の凸結合であるため、考慮から完全に除外します。

  1. これは何を意味するのでしょうか？複数の点が Po に対して同じ極角を持っている場合はどうすればよいですか?

また、私は構造を作ったとしましょう

struct points
{
    int x, y;
} P[10000];
  1. C++ STL ライブラリを使用して並べ替えステップを実装するにはどうすればよいですか? つまり、でコンパレータ関数をどのように定義すればよいsort(P+1, P+N, comparator)ですか?
4

3 に答える 3

4

これはどういう意味ですか、複数のポイントがPoに対して同じ極角を持っている場合はどうすればよいですか？

P 0が(0,0)、P 1が(1,1)、P2がであるとしましょう(2,2)。ここで、P1とP2はP0に対して同じ角度になります。この場合、P1を破棄します。同じ角度でP0とP2の間にさらにポイントがある場合は、P 2（およびもちろんP 0 ）を除くすべてを破棄します。

C ++ STL（アルゴリズムのソート関数）ライブラリを使用してソートステップをどのように実装する必要がありますか？特に、sort（P + 1、P + N、comparator）を意味します。コンパレータ機能をどのように定義すればよいですか？

C ++（STL）についてはあまり詳しくありませんが、atan2使用できる機能があるかどうかを確認してください。参照：水平軸に対応する2点間の角度を見つけますか？線と横軸の間の角度を計算する方法は？

于 2012-07-13T08:45:03.787 に答える
3

C ++での凸包のガラムスキャンアルゴリズムの実装は次のとおりです

struct vert
{
    int x,y;
    float rad;
    int idx;
};    
bool operator<(const vert &a,const vert &b)//this is the function u are looking for
{
    if(a.rad<b.rad)
        return true;
    if(a.rad==b.rad)
    {
        if(a.y>b.y)
            return true;
        else if(a.y==b.y&&a.x>b.x)
            return true;
        else
            return false;
    }
    return false;
}    
vert operator-(vert x,vert y)
{
    vert tmp;
    tmp.x=x.x-y.x;
    tmp.y=x.y-y.y;
    return tmp;
}
double dist(vert a,vert b)
{
    vert ab=b-a;
    return sqrt(ab.x*ab.x+ab.y*ab.y);
}
int cross(vert a,vert b,vert c)
{
    vert ab,bc;
    ab=b-a;
    bc=c-b;
    return ab.x*bc.y-ab.y*bc.x;
}
int main()
{
    int t,i,j,k,n;
    //("example.txt","r",stdin);
    scanf("%d",&t);
    vert a[100009],point[100009];
    int kx,ky;
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
            a[i].idx=i+1;
        }
        vert d;
        d=a[0];
        for(i=1;i<n;i++)
        {
            if(a[i].y<d.y)
                d=a[i];
            else if(a[i].y==d.y&&a[i].x<d.x)
                d=a[i];
        }
        vector<vert> v;
        for(i=0;i<n;i++)
        {
            kx=a[i].x-d.x;
            ky=a[i].y-d.y;
            if(kx==0&&ky==0)
                continue;
            a[i].rad=atan2(kx,ky)*-1.00;
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        float rad=-10000;
        j=0;
        for(i=0;i<v.size();i++)
        {
            if(v[i].rad!=rad)
            {
                a[j++]=v[i];
                rad=v[i].rad;
            }
        }
        k=0;
        point[k++]=d;
        for(i=0;i<j;i++)
        {
            if(k<=1)
                point[k++]=a[i];
            if(cross(point[k-2],point[k-1],a[i])>0)
            {
                point[k++]=a[i];
            }
            else
            {
                do
                {
                    k--;
                    if(cross(point[k-2],point[k-1],a[i])>0)
                        break;
                }while(k>1);
                point[k++]=a[i];
            }
        }
        double dis=0;
        for(i=1;i<k;i++)
            dis+=dist(point[i],point[i-1]);
        dis+=dist(point[0],point[k-1]);
        printf("%0.2f\n",dis);
        for(i=0;i<k;i++)
            printf("%d ",point[i].idx);
        cout<<endl<<endl;;
    }
    return 0;
}

ここで行ったように、コンパレーター関数を使用するか、operator< をオーバーロードすることができます。これは同様に機能しますが、現在は sort() 関数の 3 番目の引数としてコンパレータ関数を渡す必要はありません

これが役立つことを願っています

于 2012-08-06T09:09:40.443 に答える