10553 - Treasure Map
Moderator: Board moderators
10553 - Treasure Map
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.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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]
[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]
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.
(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.
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 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.
The image is not loaded properly. I give the http address below:
http://www.geocities.com/martoro/acm/Example.bmp
http://www.geocities.com/martoro/acm/Example.bmp
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
The link works with me. I put jpg image instead of bmp.
![Image](http://www.geocities.com/martoro/acm/example.jpg)
The link is:
http://www.geocities.com/martoro/acm/example.jpg
![Image](http://www.geocities.com/martoro/acm/example.jpg)
The link is:
http://www.geocities.com/martoro/acm/example.jpg
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.
Now it works (the llink, that is).
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.
You are rotating in the wrong direction.