10553 - Treasure Map

BiK · Post by **BiK** » Fri Sep 26, 2003 5:22 pm

Can anyone tell me how this problem should be solved. I tried direct algorithm and then rotation of the wrong X point with the angle of the deviation from real north but I got WA.

little joey · Post by **little joey** » Fri Sep 26, 2003 6:53 pm

That's what I did, and got accepted.
Did you rotate in the right direction? Can you reproduce the example data? Do some hand simulations with small data sets to get a feeling for the critical data.

Larry · Post by **Larry** » Fri Sep 26, 2003 7:42 pm

Ya, the test cases work if you rotate the other way, which was why I got mine wrong.. but ya, it's pretty much straightforward otherwise..

BiK · Post by **BiK** » Sat Sep 27, 2003 2:38 am

What's wrong with my program. It gets wrong answer whichever direction of rotation a choose

[cpp]
#include <iostream.h>
#include <iomanip.h>
#include <math.h>
#include <string.h>

const int DIRS = 32;
const int DIR_LEN = 7;
const int MAX_PATH_LEN = 1000;
const double PI = acos(-1);

char dirs[DIRS][DIR_LEN] = {
"N",
"NbE",
"NNE",
"NEbN",
"NE",
"NEbE",
"ENE",
"EbN",
"E",
"EbS",
"ESE",
"SEbE",
"SE",
"SEbS",
"SSE",
"SbE",
"S",
"SbW",
"SSW",
"SWbS",
"SW",
"SWbW",
"WSW",
"WbS",
"W",
"WbN",
"WNW",
"NWbW",
"NW",
"NWbN",
"NNW",
"NbW"
};

char path[MAX_PATH_LEN][DIR_LEN];

int steps[MAX_PATH_LEN+1];

double points[MAX_PATH_LEN + 1][2];

int n;

double getAngle(int i) {
bool found = false;
int k = 0;
while(!found) {
if (!strcmp(dirs[k], path)) {
found = true;
break;
}

k++;
}

if (k < 24)
return PI / 2 - k * 11.25 * PI / 180;
else
return 5 * PI / 2 - k * 11.25 * PI / 180;
}

void findXPoint(double &x, double &y, double dev) {
for(int i = 0;i < n;i++) {
double alpha = getAngle(i) - dev * PI / 180;
x = x + cos(alpha) * steps;
y = y + sin(alpha) * steps;
}
}

double distance(double x1, double y1, double x2, double y2) {
return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}

void findPoints(double points[][2]) {
points[0][0] = 0;
points[0][1] = 0;
for(int i = 0;i < n;i++) {
double alpha = getAngle(i);
points[i+1][0] = points[0] + cos(alpha) * steps;
points[i+1][1] = points[1] + sin(alpha) * steps;
}
}

double minDist(double x, double y) {
double min = distance(points[0][0], points[0][1], x, y);
for(int i = 1;i <= n;i++) {
double dist = distance(points[0], points[1], x, y);
if (dist < min)
min = dist;
}

return min;
}

double calc2(double dev) {
findPoints(points);
double alpha = dev * PI / 180;
double Xx = cos(alpha) * points[n][0] + sin(alpha) * points[n][1];
double Xy = -sin(alpha) * points[n][0] + cos(alpha) * points[n][1];
/*double Xx = cos(alpha) * points[n][0] - sin(alpha) * points[n][1];
double Xy = sin(alpha) * points[n][0] + cos(alpha) * points[n][1];*/

return minDist(Xx, Xy);
}

double calc(double dev) {
double Xx,Xy;
findXPoint(Xx, Xy, dev);
double min = distance(0, 0, Xx, Xy);
double x = 0;
double y = 0;
for(int i = 0; i < n;i++) {
double alpha = getAngle(i);
x = x + cos(alpha) * steps;
y = y + sin(alpha) * steps[i];
double dist = distance(x, y, Xx, Xy);
if (dist < min)
min = dist;
}

return min;
}

void main() {
while(true) {
cin >> n;
if (!n)
break;
for(int i = 0;i < n;i++) {
cin >> path[i];
cin >> steps[i];
}
double dev;
cin >> dev;
double dist = calc2(dev);
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
cout << sqrt(dist) << endl;
}
}[/cpp]

gvcormac · Post by **gvcormac** » Sat Sep 27, 2003 4:20 am

Sorry to be provocative, but what's *right* with your program. Why don't you try to prove to us that it is correct. Then, I daresay, you'll figure out your problem yourself or at least give somebody a freamework to show where you went wrong.

BiK · Post by **BiK** » Sat Sep 27, 2003 2:07 pm

What the program does is to find the points on my way to the treasure the first time I was on the island - findPoints(). The starting point is O(0,0) - the origing of the coordinate system. The last point is the false X point - that is where the treasure was supposed to be. The point where the treasure is actually located can be found if we rotate the false X point with the angle of the deviation from real North (I tried rotating clockwise and counterclockwise). The rotation is a simple liner transformation with matrix:

(cos x, -sin x)
(sin x, cos x)

or

(cos x, sin x)
(-sin x, cos x)

depending on the direction of rotation. It is performed in [cpp]double calc2(double dev)[/cpp]. dev is the angle of deviation in degrees.

Finally [cpp]double minDist(double x, double y)[/cpp] takes as arguments the coordinates of the actual spot of the treasure and calculates for every point on the wrong path the distance to the treasure location. The returned result is the minimal such distance.

[cpp]double getAngle(int i)[/cpp] takes as argument the index of one of the 32 possible directions and returns the angle in radians for the usual coordinate system:

........ N
W......O(0,0).......E
.........S

I get WA. I tried also looking for some careless mistake but I couldn't find any.

Lain · Post by **Lain** » Sat Sep 27, 2003 2:21 pm

Input:
2
NE 2
S 1
-90

Output:
1.29

Check it!

gvcormac · Post by **gvcormac** » Sat Sep 27, 2003 2:45 pm

BiK wrote:What the program does is to find the points on my way to the treasure the first time I was on the island - findPoints().

[snip]

I get WA. I tried also looking for some careless mistake but I couldn't find any.

Perfect. Your description enables me to see you're oversight. I think Lain's example will help you to see it if you draw a picture.

BiK · Post by **BiK** » Sat Sep 27, 2003 4:00 pm

I draw an image of the Lain's sample input but I think that the correct answer is 1.47 (which my program calculates) not 1.29.

I was closest to the treasure when I was at O(0,0). And the length of the segment is 1.47.

BiK · Post by **BiK** » Sat Sep 27, 2003 4:07 pm

The image is not loaded properly. I give the http address below:

http://www.geocities.com/martoro/acm/Example.bmp

gvcormac · Post by **gvcormac** » Sat Sep 27, 2003 4:22 pm

BiK wrote:The image is not loaded properly. I give the http address below:

http://www.geocities.com/martoro/acm/Example.bmp

Geocities says there is no such page.

In any event, I'm sure your diagram is correct. Read the question carefully and figure out why the correct output is 1.29

BiK · Post by **BiK** » Sat Sep 27, 2003 4:45 pm

The link works with me. I put jpg image instead of bmp.

The link is:

http://www.geocities.com/martoro/acm/example.jpg

gvcormac · Post by **gvcormac** » Sat Sep 27, 2003 4:50 pm

BiK wrote:The link works with me. I put jpg image instead of bmp.

The link is:

http://www.geocities.com/martoro/acm/example.jpg

Yahoo!

This page is not available.
We're sorry, but this page is currently unavailable for viewing.
If this site belongs to you, please read this help page for more information and assistance.

For general questions see our main help area, or search for other member pages.

BiK · Post by **BiK** » Sat Sep 27, 2003 4:54 pm

Are you saying that I should take into consideration all points along the path and not only the endpoints of the segments?

gvcormac · Post by **gvcormac** » Sat Sep 27, 2003 4:58 pm

Yahoo!

This page is not available.
We're sorry, but this page is currently unavailable for viewing.
If this site belongs to you, please read this help page for more information and assistance.

For general questions see our main help area, or search for other member pages.

Now it works (the llink, that is).

You are rotating in the wrong direction.