I have to implement Graham Scan Algorithm. This is my code:
/*
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 end
S.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;
}
It's not working in sorting section. Functions _arctan2() and _sqrt() have returning large values. I.e sqrt returns -1464986461. Why it happens? As a result, points are not sorted by alfa, but in not known way. If I manual set order of points, algorithm work properly.
Could you tell me way it is not working?
You're trying to print a floating point value as a decimal (int) value.
Do this instead:
%dmeans signed decimal integer. Review the documentation for printf%fmeans decimal floating point