#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//Our typedef for our sheep.
struct sheep
{
int x;
int y;
int sheepNumber;
struct sheep *nextSheep;
};
typedef struct sheep sheep;
//We will set up our pruning array.
sheep* prune(sheep*);
int main (int argc, const char * argv[])
{
int numLoops;
scanf("%d",&numLoops);
fgetc(stdin);
while(numLoops)
{
int numSheep;
scanf("%d",&numSheep);
fgetc(stdin);
sheep *headSheep, *currSheep;
headSheep=NULL;
int counter;
//Make a linkedList of sheep. This SHOULD be easier to prune later.
for(counter=0;counter<numSheep;counter++)
{
currSheep = (sheep*)malloc(sizeof(sheep));
scanf("%d",&currSheep->x);
getchar();
scanf("%d",&currSheep->y);
getchar();
currSheep->sheepNumber=counter+1;
currSheep->nextSheep=headSheep;
headSheep = currSheep;
}
currSheep=headSheep;
/*while(currSheep)
{
printf("%d\n",currSheep->sheepNumber);
currSheep=currSheep->nextSheep;
}*/
//Input is now in for the test case. If there is one sheep it's a special case, and we can deal with it like so
if(numSheep==1)
{
printf("0.00\n1\n");
}
//Else we must calculate the size of our fence. To do this we must organize our list. We will be pruning before this.
else
{
sheep *newSheep = prune(currSheep);
sheep *printSheep = newSheep;
//We now need a search method...can we compile this in C++ and just use the provided sort?
while(printSheep)
{
printf("%d\n",printSheep->sheepNumber);
printSheep=printSheep->nextSheep;
}
}
numLoops--;
}
return 0;
}
sheep* prune (sheep *inputSheep)
{
int aValue, bValue, cValue, dValue;
int xPlusY, xMinusY;
int aX,aY,bX,bY,cX,cY,dX,dY;
xPlusY = inputSheep->x + inputSheep->y;
xMinusY = inputSheep->x - inputSheep->y;
cValue = xMinusY;
dValue = xPlusY;
cX = inputSheep->x;
dX = inputSheep->x;
cY = inputSheep->y;
dY = inputSheep->y;
//Store the first sheep in headSheep
sheep headSheep = *inputSheep;
inputSheep = inputSheep->nextSheep;
xPlusY = inputSheep->x + inputSheep->y;
xMinusY = inputSheep->x - inputSheep->y;
if(xPlusY > dValue)
{
bValue = xPlusY;
bX = inputSheep->x;
bY = inputSheep->y;
}
else
{
bValue = dValue;
bX = dX;
bY = dY;
}
if(xMinusY > cValue)
{
aValue = xMinusY;
aX = inputSheep->x;
aY = inputSheep->y;
}
else
{
aValue = cValue;
aX = cX;
aY = cY;
}
int rX1,rX2,rY1,rY2;
//We have now set up the first four a,b,c and d points. We can now begin to extend our a,b,c and d along our linked list until we reach NULL, or the end (sheep==1) of the list.
while(inputSheep->nextSheep!=NULL)
{
inputSheep = inputSheep->nextSheep;
xPlusY = inputSheep->x + inputSheep->y;
xMinusY = inputSheep->x - inputSheep->y;
if(xPlusY>bValue || xPlusY<dValue)
{
if(xPlusY>bValue)
{
bValue = xPlusY;
bX = inputSheep->x;
bY = inputSheep->y;
}
else
{
dValue = xPlusY;
dX = inputSheep->x;
dY = inputSheep->y;
}
}
if(xMinusY>aValue || xMinusY<cValue)
{
if(xMinusY>aValue)
{
aValue = xMinusY;
aX = inputSheep->x;
aY = inputSheep->y;
}
else
{
cValue = xMinusY;
cX = inputSheep->x;
cY = inputSheep->y;
}
}
}
rX1 = (cX>dX) ? cX : dX;
rX2 = (aX>bX) ? bX : aX;
rY1 = (aY>dY) ? aY : dY;
rY2 = (bY>cY) ? cY : bY;
sheep *preceding = &headSheep;
sheep *current;
while((preceding->x>rX1 && preceding->x<rX2) && (preceding->y>rY1 && preceding->y<rY2))
{
preceding = preceding->nextSheep;
}
//Now we have a good starting point for freeing up our list
sheep *firstSheep = preceding;
current = preceding->nextSheep;
while(current!=NULL)
{
if((current->x>rX1 && current->x<rX2) && (current->y>rY1 && current->y<rY2))
{
preceding->nextSheep = current->nextSheep;
free(current);
current = preceding->nextSheep;
}
else
{
preceding = current;
current = current->nextSheep;
}
}
sheep *secondSheep = firstSheep;
return secondSheep;
}
I cannot work out why my pointers are messing me around here. Given this as input:
1
5
0 0
0 5
10 5
3 3
10 0
My anticipated output is :
5
3
2
1
However, my program prints out 5, then crashes.
I am trying to follow the thread using XCode, and I find that the program has the same address for firstSheep and secondSheep when it returns. This is transferred into newSheep. Additionally, I can put that same address into printSheep, and during this whole time, for the duration of their existance, all the pointers contain the address, and the data they contain is the correct flow.
The program then prints 5, and following this moves to the next statement. At this point rather than fetching the address given by the nextSheep, it returns a random address, and crashes. I'm not sure what's causing this. To give some clue, I can fix the error by including this statement at the bottom of prune:
sheep *secondSheep = firstSheep;
while(firstSheep)
{
printf("%d",firstSheep->sheepNumber);
firstSheep=firstSheep->nextSheep;
}
return secondSheep;
I have embedded the code within two existing lines so it can be more easily identified exactly where I place it.
If I do this, my output is:
53215
3
2
1
Obviously this is undesireable, as it leaves me printing two strings. Outside of this, it is very confusing to me that the program would not work, unless a while loop that prints an unrelated variable is given. firstSheep is not returned, and the while loop does no pointer modifications that could possibly affect secondSheep.
Please I know this is a long post but if I could get someone to confirm this or localize it to my computer, or maybe even point out my mistake that would be great!
Thanks,
TLE
