Я должен реализовать алгоритм сканирования Грэма.
Это мой код:
/*
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. Почему так происходит?
В результате баллы сортируются не по альфа, а неизвестным способом. Если я вручную установлю порядок точек, алгоритм будет работать правильно.
Не могли бы вы сказать мне, как это не работает?
Вы пытаетесь напечатать значение с плавающей запятой в виде десятичного (целого) значения.
Сделайте это вместо этого:
printf("alpha= %f, r= %f \n",arrayAR[i].alpha,arrayAR[i].r);
%d
означает подписанное десятичное целое число. Обзор документация для печати
%f
означает десятичную с плавающей точкой
Хорошо, теперь это работает:
/*
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;
}