206 - Meals on Wheels Routing System

[GreenPenInc]

Is there some weird test case? My program handles the input perfectly. I sort by angle, distribute them OK, and it still doesn't work. Anyone get AC on this and have any insight to share?

[GreenPenInc]

[cpp]
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <string>
#include <cstring>

#define PI 3.1415926535898

using namespace std;

typedef struct point
{
point()
{
x = 0.0;
y = 0.0;
}
point(double x1, double y1)
{
x = x1;
y = y1;
}
double r()
{
return sqrt(x * x + y * y);
}
double degrees()
{
double temp = atan2(y, x) * 180 / PI;
if (temp < 0) temp += 360;
return temp;
}
double x;
double y;
};

typedef struct customer
{
void display()
{
//cout << "Customer: " << name << " (" << loc.x << ", " << loc.y << ")" << endl;
cout << "Customer: " << name << " " << loc.degrees() << "\t" << loc.r() << endl;
}
double distance(point p)
{
return abs(p.x - loc.x) + abs(p.y - loc.y);
}
point loc;
char name[25];
};

typedef struct node
{
node() {}
node(customer c, node * n)
{
data = c;
next = n;
}
double r()
{
return data.loc.r();
}
double degrees()
{
return data.loc.degrees();
}
customer data;
node * next;
};

node * header;

void ordered_insert(customer c)
{
if (header == 0 || c.loc.degrees() < header->degrees())
header = new node(c, header);
else
{
node * curr = header;
node * prev;
while (curr != 0)
{
if (curr->degrees() > c.loc.degrees() || (curr->degrees() == c.loc.degrees() && curr->r() > c.loc.r())) break;
prev = curr;
curr = curr->next;
}
prev->next = new node(c, curr);
}
}

int display_route(node * first, int count)
{
point p(0, 0);
int dist = 0;
node * curr = first;
for (int i = 0; i < count; i++)
{
dist += (int)(fabs(p.x - curr->data.loc.x) + fabs(p.y - curr->data.loc.y) + 0.5);
cout << "Customer: " << curr->data.name << endl;
p = curr->data.loc;
curr = curr->next;
}
dist += (int)(fabs(p.x) + fabs(p.y) + 0.5);
cout << "Route Length ==> " << dist << endl;
return dist;
}



int main()
{
customer c;
node * curr;
int drivers, customers, total_route_length;
char name[25], id[50];
int x, y;
char thingy[37] = "";
while (1)
{
total_route_length = 0;
cin.getline(id, 50);
if (cin.gcount() == 0) break;
cout << thingy;
strcpy(thingy, "************************************\n");
header = 0;
cin >> drivers >> customers;
cin.ignore(1, '\n');
for (int i = 0; i < customers; i++)
{
cin.getline(name, 25);
cin >> x >> y;
cin.ignore(1, '\n');
c.loc = point(x, y);
strcpy(c.name, name);
ordered_insert(c);

}
cout << id << endl;
cout << "Number of Customers: ";
printf("%-11d Number of Routes: ", customers);
cout << drivers << endl;
curr = header;
for (int i = 0; i < drivers; i++)
{
int num_custs = customers / drivers;
if (i < customers % drivers) num_custs++;
cout << endl << "Route ==> " << (i + 1) << endl;
total_route_length += display_route(curr, num_custs);
for (int j = 0; j < num_custs; j++)
curr = curr->next;
}
cout << endl << "Total Route Length ==> " << total_route_length << endl;
}
}
[/cpp]

Incidentally, this is my source code if that would help. (I already tried adjusting the lengths of the asterisks; it didn't work. And I'm still getting WA.)

[Adrian Kuegel]

Be careful when comparing two double values.
It shouldn't be if (curr->degrees() > c.loc.degrees() || (curr->degrees() == c.loc.degrees() && curr->r() > c.loc.r())) break;
you should use:
if (curr->degrees()>=c.loc.degrees()+1e-6 || fabs(curr->degrees() - c.loc.degrees())<1e-6 && curr->r() > c.loc.r())) break;

[GreenPenInc]

Thanks, but still WA. And that seems rather like a shortcoming of the language, does it not?

[Per]

It's rather a shortcoming of not using hardware with infinite precision.

[GreenPenInc]

Right, I understand that, but I'd think the language would be able to handle equality of doubles. What I'm trying to say is that atan2(3, 4) and atan2(36, 48) should return precisely the same double value, for example.

Anyway, any further insights on this problem? It produces precisely the required output on the test cases (I used diff to check) and it still won't accept my answer. What's galling is that it's not even that difficult of a problem!

[Adrian Kuegel]

id has up to 50 characters, so you have to allocate 51 characters (remember the \0 that is used to indicate the end of the string).
Same applies to name, you have to reserve 26 characters.
Just a simple rule: always use arrays a bit bigger than needed, so you don't have to think about that \0.
And why don't you use the qsort function of <stdlib.h>? or sort of <algorithm> ? It makes things a lot easier.

[GreenPenInc]

Thanks for your help! I changed the array lengths to accommodate, as I should have done from the beginning. A very humbling experience, to be sure. Now I am getting a Runtime Error. I should upload my code again:

[cpp]
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <string>
#include <cstring>

#define PI 3.1415926535898

using namespace std;

typedef struct point
{
point()
{
x = 0.0;
y = 0.0;
}
point(double x1, double y1)
{
x = x1;
y = y1;
}
double r()
{
return sqrt(x * x + y * y);
}
double degrees()
{
double temp = atan2(y, x) * 180 / PI;
if (temp < 0) temp += 360;
return temp;
}
double x;
double y;
};

typedef struct customer
{
void display()
{
//cout << "Customer: " << name << " (" << loc.x << ", " << loc.y << ")" << endl;
cout << "Customer: " << name << " " << loc.degrees() << "\t" << loc.r() << endl;
}
double distance(point p)
{
return abs(p.x - loc.x) + abs(p.y - loc.y);
}
point loc;
char name[27];
};

typedef struct node
{
node() {}
node(customer c, node * n)
{
data = c;
next = n;
}
double r()
{
return data.loc.r();
}
double degrees()
{
return data.loc.degrees();
}
customer data;
node * next;
};

node * header;

void ordered_insert(customer c)
{
if (header == 0 || c.loc.degrees() < header->degrees())
header = new node(c, header);
else
{
node * curr = header;
node * prev;
while (curr != 0)
{
if (curr->degrees() > c.loc.degrees() || fabs(curr->degrees() - c.loc.degrees()) <= 1e-6 && curr->r() > c.loc.r()) break;
prev = curr;
curr = curr->next;
}
prev->next = new node(c, curr);
}
}

int display_route(node * first, int count)
{
point p(0, 0);
int dist = 0;
node * curr = first;
for (int i = 0; i < count; i++)
{
dist += (int)(fabs(p.x - curr->data.loc.x) + fabs(p.y - curr->data.loc.y) + 0.5);
cout << "Customer: " << curr->data.name << endl;
p = curr->data.loc;
curr = curr->next;
}
dist += (int)(fabs(p.x) + fabs(p.y) + 0.5);
cout << "Route Length ==> " << dist << endl;
return dist;
}



int main()
{
customer c;
node * curr;
int drivers, customers, total_route_length;
char name[27], id[52];
int x, y;
char thingy[37] = "";
while (1)
{
total_route_length = 0;
cin.getline(id, 51);
if (cin.gcount() == 0) break;
cout << thingy;
strcpy(thingy, "***********************************\n");
header = 0;
cin >> drivers >> customers;
if (cin.peek() == '\n') cin.get();
for (int i = 0; i < customers; i++)
{
cin.getline(name, 26);
cin >> x >> y;
if (cin.peek() == '\n') cin.get();
c.loc = point(x, y);
strcpy(c.name, name);
ordered_insert(c);

}
cout << id << endl;
cout << "Number of Customers: ";
printf("%-10d Number of Routes: ", customers);
cout << drivers << endl;
curr = header;
for (int i = 0; i < drivers; i++)
{
int num_custs = customers / drivers;
if (i < customers % drivers) num_custs++;
cout << endl << "Route ==> " << (i + 1) << endl;
total_route_length += display_route(curr, num_custs);
for (int j = 0; j < num_custs; j++)
curr = curr->next;
}
cout << endl << "Total Route Length ==> " << total_route_length << endl;
}
}
[/cpp]

The only thing I changed was the length of the strings, Specifically, I can change the length of id with no problem whatsoever, but once I then proceed to make the name longer it crashes on Valladolid while running fine on my computer.

The reason I didn't use those sort functions was because I didn't know about them, or how to use them. Besides, I figured a simple ordered insert would work just fine.

Thanks for your continued help; this has been very humbling for me.

[Adrian Kuegel]

I think you still have problems in your sorting routine.
Here is a compare function that would give you true, if customer a is smaller than customer b, that means the degrees of his location is smaller or he is nearer to the origin.
bool operator<(customer a, customer b) {
if (fabs(a.loc.degrees()-b.loc.degrees())>1e-6)
return a.loc.degrees()<b.loc.degrees();
return a.loc.r()<b.loc.r();
}

Now you can use the < operator to compare two customers.
And to use sort, you just need to include <algorithm> and then you write:
sort(array,array+number_of_elements);
this function uses the operator< of the given array type for comparison and sorts your array.

[GreenPenInc]

How about that eh? I got accepted!

I think I learned a valuable lesson here but it might take some time for me to figure out what that is. Thanks again for your kind and patient help; I hope to be able to do the same for others who struggle in the future.

[locke]

I'm trying to submit my sol. to problem 206, but keep getting compile error! I've confirmed that it works fine both on my debian box (g++ (GCC) 3.3.5 (Debian 1:3.3.5-13)), and on my school's FreeBSD box, g++ version 2.95.4, which I hear is exactly what the judge uses (minus the FreeBSD I guess).

It compiles perfectly fine on all of those boxes, and gives no warnings when I use the -Wall flag.

I have not been e-mailed any compile output from the judge, but was wondering if there was a way I could get it. Ideally, I'd like to view it online, but I bet that's not a possibility.

cheers

[locke]

ugh.... it was M_PI. Why I was able to compile all over the place with the -ansi flag, I'm not sure...

[deadangelx]

I think the only trick of this problem is to calculate angle.

except 0, 90, 180, 270 degree angle, you can use the formula:

Code: Select all

 
a = atan2( fabs( y-cordinate ), fabs( x-cordinate ) ) * ( 45 / atan( 1.0 ) );

And,

Code: Select all

in 1st quadrant angle is just a.
in 2nd quadrant angle is 180 - a
in 3rd quadrant angle is 180 + a
in 4th quadrant angle is 360 - a

Hope it helps.