Graham의 convex hull을 찾는 알고리즘에 영향을주는 알 수없는 버그

Question

Graham의 알고리즘을 프로그래밍했지만 여전히 convex hull에 대한 잘못된 점을 제공합니다. 도움이 필요해. 내 사인 기능에 버그가 있다고 생각하지만 그것이 무엇인지 모르겠다.

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

기호 내가 모든 벡터를 반복하고 볼록 선체

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

에게 인쇄 볼록 선체 여기

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); 
    } 

의 포인트를 결정하려고

여기

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; 

두 배로 사용 개선

Answer 1

마이 큐 왜 int f(pair<int, int>, pair<int, int>)이 pair<double, double> 대신 pair<int, int>일까요?

또한 왜 compare_blah과 같은 유익한 이름이 지정되지 않았습니까?

마지막으로 대신 bool을 반환하지 않는 이유는 무엇입니까? 어느 쪽이든 당연히 작동하지만, bool을 돌려 주면 단순히 비교 기능으로 만 사용된다는 것을 분명히 알 수 있습니다. 그리고 그것을 읽은 사람들에게 프로그램을 명확하게하는 것이 주 목표가되어야합니다. 그것이하는 일을하는 것이 부차적 인 목표입니다. 결국, 그것이해야 할 일을하는 것은 일시적인 일시적인 현상 일뿐입니다. 결국 누군가 다른 일을하기를 원할 것입니다.

pair<int, int> 문제가있을 수 있습니다. 해당 함수에서 암시적인 형식 변환을 int과 double 사이에서하고 정보를 왼쪽과 오른쪽으로 잃어 버리고 있습니다. 나는 그것이 당신이 의도 한 바가 의심 스럽습니다.

당신이 당신의 pairtypedef pair<double, double> point2d_t 등의 형식 정의를 사용하고 같은 실수로부터 자신을 보호하고 거래의 프로그램이 명확하게 수있는 모든 곳에서 다음 point2d_t을 사용합니다.

그레이엄의 알고리즘으로 abs의 사용을 f으로 평가하는 데 익숙하지는 않지만이 문제에 대해 의견을 개진 한 사람이 정확할 수도 있습니다.