影響Graham算法尋找凸包的未知錯誤

Question

我已經編程了Graham算法，但它仍然給我凸點的錯誤點。我需要幫助。認爲我在我的登錄功能中有一個錯誤，但不知道它是什麼。

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

Answer 1

我的問題爲什麼int f(pair<int, int>, pair<int, int>)需要pair<int, int>而不是pair<double, double>？

此外，爲什麼它不被命名爲信息如compare_blah？

最後，爲什麼不返回bool而不是int？當然可以工作，但是如果你返回一個bool，它將會更清楚地表明這只是一個比較函數。並且讓讀者閱讀它的程序應該是你的主要目標。讓它做它應該是次要的目標。畢竟，它所做的只是過渡性的事情。最終有人會希望它做別的。

pair<int, int>事情可能是你的問題。您正在執行int和double之間的該函數中的幾個隱式類型轉換，並丟失左側和右側的信息。我懷疑這是你的意圖。

，如果您使用typedef爲您pair像typedef pair<double, double> point2d_t然後用point2d_t無處不在，你可以保護自己免受這樣的錯誤，使你的程序在討價還價清晰。

我對格雷厄姆的算法不夠熟悉，用於評估您在f之內對abs的使用，雖然很可能評論此問題的人是正確的。