Алгоритм сканирования Грэма — & gt; sqrt и arctan2 огромные значения

Я должен реализовать алгоритм сканирования Грэма.
Это мой код:

    /*
Graham's algorithm'
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#include <stack>
#include <vector>
#include <math.h>

#include <algorithm>
#include <cstdlib>

using namespace std;
struct Tpoint
{
int x;
int y;
};

struct AR{
double alpha;
double r;
int i;
};bool operator<(AR p, AR q){
if(p.alpha != p.alpha){
return p.alpha < p.alpha;
} else {
return p.r < p.r;
}
}int det(Tpoint p1, Tpoint p2, Tpoint p3){
return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y;
}int right_turn(stack<Tpoint,vector<Tpoint> > S,Tpoint p3){
Tpoint p2;
Tpoint p1;p2=S.top();
S.pop();
p1=S.top();
S.push(p2);if (det(p1,p2,p3)>0)
return 0;if (det(p1,p2,p3)<0)
return 1;
}

int main(){

vector<Tpoint> Q;

//Stos pointów, na końcu zawiera wynik
stack<Tpoint,vector<Tpoint> > S;

Tpoint point;Tpoint array[]={3,-2, -3,-2, 6,4, -6,1, 4,5, 0,0, 3,4, -3,3, -2,2, 0,6};
Tpoint point00=array[0];
int xMax = array[0].x;
int yMin = array[0].y;
int i;
for (i=0; i<10; i++){
if (array[i].y<yMin){
if(array[i].x>xMax){
xMax=array[i].x;
yMin=array[i].y;
point00=array[i];}
}
}

//sorting section start

printf("%d %d \n \n",point00.x, point00.y);
Q.push_back(point00);

Tpoint arrayCLONE[10];
AR arrayAR[10];
for (i=0; i<10; i++){
arrayAR[i].alpha=0.0;
arrayAR[i].r=0.0;
arrayAR[i].i=i;
arrayCLONE[i] = array[i];

array[i].x-=point00.x;
array[i].y-=point00.y;

}for (i=0; i<10; i++){
if ((array[i].x != point00.x) && (array[i].y != point00.y)) {
arrayAR[i].alpha=atan2(array[i].y, array[i].x);
arrayAR[i].r=sqrt(array[i].x*array[i].x+array[i].y*array[i].y);printf("alpha= %d, r= %d \n",arrayAR[i].alpha,arrayAR[i].r);
printf("x= %d, y= %d\n",array[i].x, array[i].y);
}else{

arrayAR[i].alpha=9999;
arrayAR[i].r=9999;
arrayAR[i].i=0;
}

}

sort (arrayAR, arrayAR + 10);

for (i=0; i<10; i++){
if (arrayAR[i].alpha<1000){
Q.push_back(arrayCLONE[arrayAR[i].i]);
//  printf("i =%d \n",i);
printf("x =%d \n",arrayCLONE[arrayAR[i].i].x);
printf("y =%d \n",arrayCLONE[arrayAR[i].i].y);
printf("_____ \n");

//  printf("index i =%d \n",arrayAR[i].i);
}
}//sorting section endS.push(Q[0]);
S.push(Q[1]);
S.push(Q[2]);

for (int i=3;i<10; i++){
while (right_turn(S,Q[i])==1)
S.pop();
S.push(Q[i]);
}printf("points: \n");
while (!(S.empty()))
{
point=S.top();
S.pop();
printf("(%d,%d) ",point.x,point.y);
}
printf("\n..");
getch();
return 0;
}

Это не работает в разделе сортировки. Функции _arctan2 () и _sqrt () возвращают большие значения. Т.е. sqrt возвращает -1464986461. Почему так происходит?
В результате баллы сортируются не по альфа, а неизвестным способом. Если я вручную установлю порядок точек, алгоритм будет работать правильно.

Не могли бы вы сказать мне, как это не работает?

0

Решение

Вы пытаетесь напечатать значение с плавающей запятой в виде десятичного (целого) значения.

Сделайте это вместо этого:

printf("alpha= %f, r= %f \n",arrayAR[i].alpha,arrayAR[i].r);

%d означает подписанное десятичное целое число. Обзор документация для печати

%f означает десятичную с плавающей точкой

1

Другие решения

Хорошо, теперь это работает:

    /*
Graham's algorithm'
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#include <stack>
#include <vector>
#include <math.h>

#include <algorithm>
#include <cstdlib>

using namespace std;
struct Tpoint
{
int x;
int y;
};

struct AR{
double alpha;
double r;
int i;
};bool operator<(AR p, AR q){
if(p.alpha != q.alpha){
return p.alpha < q.alpha;
} else {
return p.r < q.r;
}
}int det(Tpoint p1, Tpoint p2, Tpoint p3){
return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y;
}int right_turn(stack<Tpoint,vector<Tpoint> > S,Tpoint p3){
Tpoint p2;
Tpoint p1;p2=S.top();
S.pop();
p1=S.top();
S.push(p2);if (det(p1,p2,p3)>0)
return 0;if (det(p1,p2,p3)<0)
return 1;
}

int main(){

vector<Tpoint> Q;

//Stos pointów, na końcu zawiera wynik
stack<Tpoint,vector<Tpoint> > S;

Tpoint point;Tpoint array[]={-3,-2, 6,4, -6,1, 4,5, 0,6, 3,4, -3,5, 3,-2,  -2,2, 0,0, 1,1};
Tpoint point00=array[0];
int xMax = array[0].x;
int yMin = array[0].y;
int i;
for (i=1; i<9; i++){

if (array[i].y<yMin){
yMin=array[i].y;}
}for (i=1; i<9; i++){

if (array[i].y==yMin){
if(array[i].x>xMax){
xMax=array[i].x;

point00=array[i];}
}
}//sorting section start

printf("point00 x=%d y=%d \n \n",point00.x, point00.y);
Q.push_back(point00);

Tpoint arrayCLONE[11];
AR arrayAR[11];
for (i=0; i<10; i++){
arrayAR[i].alpha=0.0;
arrayAR[i].r=0.0;
arrayAR[i].i=i;
arrayCLONE[i] = array[i];array[i].x-=point00.x;
array[i].y-=point00.y;

//printf("x2= %d, y2= %d\n",array[i].x, array[i].y);
}for (i=0; i<11; i++){

if (((array[i].x != 0) || (array[i].y != 0))) {

arrayAR[i].alpha=atan2(array[i].y, array[i].x);
arrayAR[i].r=sqrt(array[i].x*array[i].x+array[i].y*array[i].y);

arrayAR[i].i=i;
printf("alpha= %f, r= %f , x= %d, y=%d\n",arrayAR[i].alpha,arrayAR[i].r,array[i].x, array[i].y);

}else{

arrayAR[i].alpha=9999;
arrayAR[i].r=9999;
arrayAR[i].i=16;
}

}

sort (arrayAR, arrayAR +10);
Tpoint temp;
for (i=0; i<10; i++){
if (arrayAR[i].alpha<1000 && arrayAR[i].alpha>0.0){

Q.push_back(arrayCLONE[arrayAR[i].i]);
//  printf("i =%d \n",i);
printf("x =%d \n",arrayCLONE[arrayAR[i].i].x);
printf("y =%d \n",arrayCLONE[arrayAR[i].i].y);
printf("_____ \n");

//  temp.x=arrayCLONE[arrayAR[i].i].x;
//  temp.y=arrayCLONE[arrayAR[i].i].y;
//  printf("index i =%d \n",arrayAR[i].i);
}
}

//Q.push_back(temp);
//sorting section endS.push(Q[0]);
S.push(Q[1]);
S.push(Q[2]);

for (int i=3;i<10; i++){
while (right_turn(S,Q[i])==1)
S.pop();
S.push(Q[i]);
}

//  S.push(Q[5]);printf("points: \n");
while (!(S.empty()))
{
point=S.top();
S.pop();
printf("(%d,%d) ",point.x,point.y);
}
printf("\n...");
getch();
return 0;
}
0

По вопросам рекламы [email protected]