2

グラハムのアルゴリズムをプログラムしましたが、それでも凸包の間違った点が得られます。私は助けが必要です。サイン関数にバグがあると思いますが、それが何であるかはわかりません。

#include <cstdio>
#include <algorithm>
#include <math.h>
#define pb push_back
#define mp make_pair
#include <vector>

using namespace std;

vector <pair<double, double> > st;
pair<double, double> p[1000];
double x, y;

int f(pair <double,double> a, pair<double, double> b)
{
    double x1 = x - a.first, x2 = x - b.first;
    double y1 = y - a.second, y2 = y - b.second;    
    return ((x1*y2-y1*x2) < 0);
}

void setlast(double &x1, double &y1, double &x2, double &y2)
{    
    x2 = st[st.size()-1].first;
    y2 = st[st.size()-1].second;
    x1 = st[st.size()-2].first;
    y1 = st[st.size()-2].second;
}

符号が改善された私は double を使用します

    double sign(double x1,double y1, double x2,double y2, double y3,double x3)
    {
        double xx1 = x2 - x1, xx2 = x3 - x1;
        double yy1 = y2 - y1, yy2 = y3 - y1;
        return (xx1*yy2-yy1*xx2);
    }

int main()
{    
    int n;
    x = 0x3f3f3f3f;
    y = 0x3f3f3f3f;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%lf %lf", &p[i].first, &p[i].second);
        if(p[i].first <= x && p[i].second <= y)
            x = p[i].first,
            y = p[i].second;
    }
    sort(p, p + n, f);
    p[n].first = x;
    p[n].second = y;
    st.pb(mp(p[0].first, p[0].second));
    st.pb(mp(p[1].first, p[1].second));
    double x1, x2, x3, y1, y2, y3;

ここで、すべてのベクトルを繰り返し処理し、凸包のポイントを決定しようとします

    for(int i = 2; i < n; i++)
    {
        x3 = p[i].first;
        y3 = p[i].second;
        setlast(x1,y1,x2,y2);
        while(1)
            if(sign(x1,y1,x2,y2,x3,y3) < 0)
            {
                st.pb(mp(x3, y3));
                break;
            }
            else
                st.pop_back(),
                setlast(x1, y1, x2, y2);
    }

ここで凸包を印刷します 

for(int i = 0; i < st.size(); i++)
        printf("%lf %lf\n", st[i].first, st[i].second);
    return 0
}
4

1 に答える 1

0

私の質問は、なぜ代わりにint f(pair<int, int>, pair<int, int>)取るのですか?pair<int, int>pair<double, double>

また、なぜ有益な名前が付けられていないのcompare_blahですか?

bool最後に、代わりに返さないのはなぜintですか? もちろんどちらも機能しますが、 を返す場合、これは単に比較関数として意図されていることがより明確になりますbool。そして、あなたのプログラムを読んだ人に分かりやすくすることが、あなたの第一の目標であるべきです。本来あるべきことを実行させることは、二次的な目標です。結局のところ、本来あるべきことを行っているのは一時的な状態にすぎません。最終的には、誰かが別のことをしたいと思うでしょう。

それpair<int, int>はあなたの問題かもしれません。intその関数で、との間でいくつかの暗黙的な型変換を行ってdoubleおり、情報が左右に失われています。それがあなたの意図したものだとは思えません。

pair自分の好きなように typedef を使用し、どこでもtypedef pair<double, double> point2d_t使用すると、point2d_tそのような間違いから身を守り、プログラムをより明確にすることができます。

abs内部の の使用を評価するほどグラハムのアルゴリズムに精通していませんfが、これについてコメントした人が正しい可能性は十分にあります。

于 2012-11-04T20:47:39.750 に答える