解題區/解題區 - UVa

UVa 10713 - Map

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Possible Output for Sample Input
  4. 4. Solution

Problem

A pirate’s treasure map typically contains a series of instructions which, if followed, lead you from the landing place on a desert isle to the spot marked X where the treasure is buried. You are to construct such a series of instructions for a particular desert isle.

The island is a circle with radius r paces whose centre is at (0,0). Relative to the centre, the point (0,1) is north, (0,-1) is south, (1,0) is east, and (-1,0) is west. Also, (1,1) is northeast, (1,-1) is southeast, (-1,1) is northwest, and (-1,-1) is southwest.

The landing place, on the circumference, is specified by its coordinates. The spot marked X, on the surface of the island is also specified by its coordinates.

Each instruction in the sequence should have the form

direction distance

where direction is one of { north, south, east, west, northeast, northwest, southeast, southwest } and distance is a non-negative real number indicating the number of paces to be travelled in the given direction. When executed as a sequence the instructions should lead from the landing place to the spot marked X without leaving the island. The total distance (that is, the sum of the distances in your sequence) should be minimized. From the possible sequences that minimize total distance, choose one with the minimum number of instructions.

Input will consist of a number of test cases, followed by a line containing -1. Each test case consists of a single line containing five real numbers: r, x, y, X, Y. r is the radius of the island; x,y are the coordinates of the landing place; X,Y are the coordinates of the spot marked X. The landing place and the spot marked X are distinct.

For each test case, output the sequence, one instruction per line. Distances should be accurate to ten places after the decimal, as shown. Output an empty line between test cases.

Sample Input

1
2
100.0 0.0 100.0 25.0 50.0
-1

Possible Output for Sample Input

1
2
south 25.0000000000
southeast 35.3553390593

Solution

題目描述：

在一個圓心島嶼上，給定登陸的座標以及寶藏的位置，只能由 8 個方向的指令，在不跑出陸地的情況下，用最少指令抵達目的地。

題目解法：

很明顯地，保證不超過兩步，但是問題在於要如何不跑出陸地上。

首先，畫一個三角形，保證能用 45 度 + 90 度的情況走到另外一個角，但是對於圓上兩點拉出來平行兩軸的矩形中，能拆分成兩個三角形，對於其中一個做就可以了。

考慮先走 45 度和 90 度其中一個，只會有兩種情況，模擬先走 45 度的情況，查閱是否超出邊界，否則倒序輸出步驟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <math.h> 
#define eps 1e-8 
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    double r, x1, x2, y1, y2;
    const double sq2 = sqrt(2);
    int cases = 0;
    while(scanf("%lf %lf %lf %lf %lf", &r, &x1, &y1, &x2, &y2) == 5) {
        if(cases++)	puts("");
        double dx = x2 - x1, dy = y2 - y1;
        if(fabs(dx) < fabs(dy)) {
            double diff = fabs(dy) - fabs(dx);
            if(dy < 0) {
                double x = x1 + dx, y = y1 - fabs(dx);
//				printf("%lf %lf\n", x, y);
                if(x*x + y*y > r*r) {
                    if(fabs(diff) > eps)
                        printf("south %.10lf\n", diff);
                    if(dx > 0)
                        printf("southeast %.10lf\n", fabs(dx) * sq2);
                    if(dx < 0)
                        printf("southwest %.10lf\n", fabs(dx) * sq2);
                } else {
                    if(dx > 0)
                        printf("southeast %.10lf\n", fabs(dx) * sq2);
                    if(dx < 0)
                        printf("southwest %.10lf\n", fabs(dx) * sq2);
                    if(fabs(diff) > eps)
                        printf("south %.10lf\n", diff);
                }
            } else {
                double x = x1 + dx, y = y1 + fabs(dx);
                if(x*x + y*y > r*r + eps) {
                    if(fabs(diff) > eps)
                        printf("north %.10lf\n", diff);
                    if(dx > 0)
                        printf("northeast %.10lf\n", fabs(dx) * sq2);
                    if(dx < 0)
                        printf("northwest %.10lf\n", fabs(dx) * sq2);
                } else {
                    if(dx > 0)
                        printf("northeast %.10lf\n", fabs(dx) * sq2);
                    if(dx < 0)
                        printf("northwest %.10lf\n", fabs(dx) * sq2);
                    if(fabs(diff) > eps)
                        printf("north %.10lf\n", diff);
                }
            }
        } else {
            double diff = fabs(dx) - fabs(dy);
            if(dx < 0) {
                double x = x1 - fabs(dy), y = y1 + dy;
                if(x*x + y*y > r*r + eps) {
                    if(fabs(diff) > eps)
                        printf("west %.10lf\n", diff);
                    if(dy > 0)
                        printf("northwest %.10lf\n", fabs(dy) * sq2);
                    if(dy < 0)
                        printf("southwest %.10lf\n", fabs(dy) * sq2);
                } else {
                    if(dy > 0)
                        printf("northwest %.10lf\n", fabs(dy) * sq2);
                    if(dy < 0)
                        printf("southwest %.10lf\n", fabs(dy) * sq2);					
                    if(fabs(diff) > eps)
                        printf("west %.10lf\n", diff);
                }
            } else {
                double x = x1 + fabs(dy), y = y1 + dy;
                if(x*x + y*y > r*r + eps) {
                    if(fabs(diff) > eps)
                        printf("east %.10lf\n", diff);
                    if(dy > 0)
                        printf("northeast %.10lf\n", fabs(dy) * sq2);
                    if(dy < 0)
                        printf("southeast %.10lf\n", fabs(dy) * sq2);
                } else {
                    if(dy > 0)
                        printf("northeast %.10lf\n", fabs(dy) * sq2);
                    if(dy < 0)
                        printf("southeast %.10lf\n", fabs(dy) * sq2);					
                    if(fabs(diff) > eps)
                        printf("east %.10lf\n", diff);
                }
            }
        }
    }
    return 0;
}
/*
    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
*/