Page 1 of 1

206 - Meals on Wheels Routing System

Posted: Wed May 05, 2004 12:58 am
by 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?

Posted: Wed May 05, 2004 10:16 pm
by 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.)

Posted: Thu May 06, 2004 10:19 am
by 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;

Posted: Thu May 06, 2004 3:18 pm
by GreenPenInc
Thanks, but still WA. And that seems rather like a shortcoming of the language, does it not?

Posted: Thu May 06, 2004 4:04 pm
by Per
It's rather a shortcoming of not using hardware with infinite precision. :)

Posted: Thu May 06, 2004 4:27 pm
by 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!

Posted: Thu May 06, 2004 4:42 pm
by 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.

Posted: Thu May 06, 2004 5:28 pm
by 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.

Posted: Thu May 06, 2004 6:22 pm
by 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.

Posted: Thu May 06, 2004 6:47 pm
by 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.

I get CE on problem and am at the end of my rope

Posted: Sun Jan 22, 2006 8:35 pm
by 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

Posted: Sun Jan 22, 2006 8:56 pm
by locke
ugh.... it was M_PI. Why I was able to compile all over the place with the -ansi flag, I'm not sure...

Re: 206 WA

Posted: Sun May 10, 2009 12:52 am
by 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.