10713 - Map

[DJY]

I try to solve p10713 but get WA

My method is go northwest/northeast/southwest/southeast first,and
then go north/south/east/west.
So there are two instructions at most .

Is there something wrong?
Plz help me

[gvcormac]

Are you staying on the island?

[medv]

Help me, please! Why WA?

#include <stdio.h>
#include <math.h>
const double EPS=0.00000000001;

void print(double DeltaX,double DeltaY)
{
if (DeltaY > EPS) printf("north");
if (DeltaY < -EPS) printf("south");
if (DeltaX > EPS) printf("east");
if (DeltaX < -EPS) printf("west");
printf(" %.10lf\n",hypot(DeltaX,DeltaY));
}

void main(void)
{
double r,x,y,X,Y;
double dx,dy,xx,yy,MinDist;
int c = 0;
while(scanf("%lf %lf %lf %lf %lf",&r,&x,&y,&X,&Y) == 5,r >= 0.0)
{
dx = X - x;
dy = Y - y;
if (c++) printf("\n");
if (dx == 0.0 || dy == 0.0 || fabs(fabs(dx) - fabs(dy)) < EPS)
{
print(dx,dy);
continue;
}
MinDist = fabs(dx) < fabs(dy) ? fabs(dx) : fabs(dy);
xx = x + (dx>0 ? MinDist : -MinDist);
yy = y + (dy>0 ? MinDist : -MinDist);
print(xx - x,yy - y);
print(X - xx,Y - yy);
}
}

[gvcormac]

Here are two immediate questions that arise when I look at your program. I suggest that it is your responsibility to explain why your program should work than to invite others to find errors.

1. What if abs(dx) == abs(dy)?

2. Where do you ensure that you stay on the island?

[medv]

if abs(dx) == abs(dy) I use

if (dx == 0.0 || dy == 0.0 || fabs(fabs(dx) - fabs(dy)) < EPS)
{
print(dx,dy);
continue;
}
and print answer.

Circle is a "convex" figure, so I do not need to check that I
stay on an island.

Give me tests where my program does not work.

[Larry]

Construct a case where you would step off the island.. =)

[anupam]

Where do you ensure that you stay on the island?

OOPS! I forgot the case. Thanks for the line. Got AC now.

[medv]

I can't understand yet.

>Where do you ensure that you stay on the island?
The problem statement says: The landing place, on the circumference, is specified by its coordinates.
And then: ... to the spot marked X without leaving the island. So my
landing place is ON the island. And my moves (vertical, horizontal
or diagonal) will NEVER lead off the island - the circle is convex.

Give me, please tests - I can't understand my mistake.

[gvcormac]

I can't understand yet.

> And my moves (vertical, horizontal
or diagonal) will NEVER lead off the island

Prove it.

[medv]

Thank you, but WA again

#include <stdio.h>
#include <math.h>
const double EPS=0.00000000001;

void print(double DeltaX,double DeltaY)
{
if (DeltaY > EPS) printf("north");
if (DeltaY < -EPS) printf("south");
if (DeltaX > EPS) printf("east");
if (DeltaX < -EPS) printf("west");
printf(" %.10lf\n",hypot(DeltaX,DeltaY));
}

void main(void)
{
double r,x,y,X,Y;
double dx,dy,xx,yy,MinDist;
int c = 0;
while(scanf("%lf %lf %lf %lf %lf",&r,&x,&y,&X,&Y) == 5,r >= 0.0)
{
dx = X - x;
dy = Y - y;
if (dx == 0.0 && dy == 0.0) continue;
if (c++) printf("\n");
if (dx == 0.0 || dy == 0.0 || fabs(fabs(dx) - fabs(dy)) < EPS)
{
print(dx,dy);
continue;
}
MinDist = fabs(dx) < fabs(dy) ? fabs(dx) : fabs(dy);
xx = x + (dx>0 ? MinDist : -MinDist);
yy = y + (dy>0 ? MinDist : -MinDist);
if (hypot(xx,yy) < r)
{
print(xx - x,yy - y);
print(X - xx,Y - yy);
} else
{
print(X - xx,Y - yy);
print(xx - x,yy - y);
}
}
}

[gvcormac]

This is a bug in gcc which is used at the uva site.

There is no "hypot" function in ansi C. The uva site compiles with the flag -ansi which
<i>should</i> give you a compile error, but doesn't. Instead it gives you incorrect
output because it links in hypot() but since there is no definition for it in <math.h>
it assumes the type is integer rather than double.

Workaround 1: include something like #define myhypot(x,y) sqrt((x)*(x)+(y)*(y)) at
the beginning of your program and replace "hypot" by "myhypot"

Workaround 2: include a declaration for hypot: double hypot(double,double)

The second workaround is easier, but not strictly ansi.

[medv]

At last AC! Thank you.

[..]

I have the practice of reading this board and website related to the solved problem.
When I see medv's source code, I just feel, medv has "almost the same" idea as the problem setter:
http://plg.uwaterloo.ca/~acm00/040919/data/A.c

Maybe medv is the person responsible for writting official solution ..........

[yohney]

I have problem with this one... Can someone give mi some tests from which I can make sure i don't have precision errors, i got WA all the time!!!

[Martin Macko]

some test cases

Code: Select all

100.000 100.0 0.000 -99.999 0.000
100.000 100.0 0.000 10.000 90.000
14.079 8.028 11.566 -0.382 0.635
14.079 8.028 11.566 7.247 -1.970
14.079 -3.414 13.659 -13.245 -2.920
14.079 -3.414 13.659 -12.584 2.838
14.079 10.440 9.446 -9.132 6.616
14.079 10.440 9.446 4.588 -9.329
57.166 -40.090 40.752 48.878 -20.636
57.166 -40.090 40.752 3.616 -39.539
57.166 -45.373 -34.774 29.370 -11.027
57.166 -45.373 -34.774 3.489 -9.819
57.166 33.251 -46.501 -31.127 10.143
57.166 33.251 -46.501 49.220 27.453
74.584 59.166 45.412 9.088 40.766
74.584 59.166 45.412 -50.984 -34.251
74.584 49.541 55.754 -43.557 -37.453
74.584 49.541 55.754 23.560 -69.849
74.584 -40.498 -62.632 0.540 6.183
74.584 -40.498 -62.632 -14.154 0.389
-1

and my AC solution output

Code: Select all

west 199.9990000000

northwest 127.2792206136

south 2.5210000000
southwest 11.8935360596

south 12.7550000000
southwest 1.1045007922

south 6.7480000000
southwest 13.9031335317

south 1.6510000000
southwest 12.9683383670

west 16.7420000000
southwest 4.0022243815

south 12.9230000000
southwest 8.2759777670

east 27.5800000000
southeast 86.8157421670

south 36.5850000000
southeast 61.8096179571

east 50.9960000000
northeast 33.5833294657

east 23.9070000000
northeast 35.2916994490

west 7.7340000000
northwest 80.1067130271

north 57.9850000000
northeast 22.5835763775

west 45.4320000000
southwest 6.5704362108

west 30.4870000000
southwest 112.6604950193

south 0.1090000000
southwest 131.6604542298

south 99.6220000000
southwest 36.7426825640

north 27.7770000000
northeast 58.0364961727

north 36.6770000000
northeast 37.2560420872