解題區/解題區 - UVa

UVa 12818 - Arc and Point

contents

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

Problem

用三個點表示一弧，求一點到一弧最段距離。

Sample Input

1
2
0 0 1 1 2 0 1 -1
3 4 0 5 -3 4 0 1

Sample Output

1
2
Case 1: 1.414
Case 2: 4.000

Solution

Imgur

Imgur

先拉 AC 一線，計算 ABC 的外心 O，判斷 ABC 張角是否大於 180 度，利用 O、B 是否在 AC 同側或異側。

接著，分配兩側開始討論，參考方式如上圖。有三角形內部問題等 …

誤差問題仍然很嚴重，用三分解法肯定過不去，倒不如說卡在要怎麼三分參數。

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x/a, y/a);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dist2(Pt a, Pt b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
Pt circle(Pt a, Pt b, Pt c) {
    Pt mab = (a + b)/2;
    Pt mbc = (b + c)/2;
    Pt lab = b - a, lbc = c - b;
    swap(lab.x, lab.y);
    swap(lbc.x, lbc.y);
    lab.x = -lab.x;
    lbc.x = -lbc.x;
    return getIntersection(mab, lab, mbc, lbc);
}
int main() {
    Pt a, b, c, p;
    int cases = 0;
    while (scanf("%lf %lf", &a.x, &a.y) == 2) {
        scanf("%lf %lf", &b.x, &b.y);
        scanf("%lf %lf", &c.x, &c.y);
        scanf("%lf %lf", &p.x, &p.y);
        double ret = min(dist(p, a), dist(p, c));
        double a1, b1, c1;
        Pt o = circle(a, b, c);
        a1 = a.y - c.y, b1 = c.x - a.x, c1 = a1 * a.x + b1 * a.y; // line ac
//        printf("%lf %lf %lf\n", a1, b1, c1);
//        printf("%lf %lf\n", a1 * b.x + b1 * b.y - c1, a1 * p.x + b1 * p.y - c1);
//        printf("%lf %lf\n", o.x, o.y);
        if ((a1 * b.x + b1 * b.y - c1 > 0) == (a1 * o.x + b1 * o.y - c1 > 0)) {
            double d = dist(o, p), r = dist(o, a);
            if ((a1 * b.x + b1 * b.y - c1 > 0) == (a1 * p.x + b1 * p.y - c1 > 0)) {
                if (cross(a, c, p) * cross(a, o, p) < eps &&
                    cross(c, o, p) * cross(c, a, p) < eps &&
                    cross(o, a, p) * cross(o, c, p) < eps) {
                } else {
                    if (d > r)
                        d -= r;
                    else
                        d = r - d;
                    ret = min(ret, d);
                }
            } else {
                if (cross(o, a, p) * cross(o, c, p) > -eps) {
                    d = d - r;
                    ret = min(ret, d);
                }
            }
        } else {
            double d = dist(o, p), r = dist(o, a);
            if ((a1 * b.x + b1 * b.y - c1 > 0) == (a1 * p.x + b1 * p.y - c1 > 0)) {
            	if (cross(o, a, p) * cross(o, c, p) < eps) {
                    if (d > r)
                        d -= r;
                    else
                        d = r - d;
                    ret = min(ret, d);
            	}
            } else {
                if (cross(a, c, p) * cross(a, o, p) < eps &&
                        cross(c, o, p) * cross(c, a, p) < eps &&
                        cross(o, a, p) * cross(o, c, p) < eps) {
                    d = r - d;
                    ret = min(ret, d);
                }
            }
        }
        assert(ret >= 0);
        printf("Case %d: %.3lf\n", ++cases, ret + eps);
    }
    return 0;
}
/*
 4 -2 -2 4 -4 -2 -1 3 
 4 -2 -2 4 -4 -2 1 3
 4 -2 -2 4 -4 -2 -3 5 
 4 -2 -2 4 -4 -2 3 5
 4 -2 -2 4 -4 -2 -3 1
 4 -2 -2 4 -4 -2 -5 1 
 4 -2 -2 4 -4 -2 -1 -1
 4 -2 -2 4 -4 -2 -1 -3 
 4 -2 -2 4 -4 -2 0 0 
 
 -4 3 0 5 4 3 9 4 
 -4 3 0 5 4 3 -9 4
 -4 3 0 5 4 3 10 3
 -4 3 0 5 4 3 -4 5
 -4 3 0 5 4 3 8 2
 -4 3 0 5 4 3 1 2
 -4 3 0 5 4 3 1 -2
 -4 3 0 5 4 3 2 1
 0 0 1 1 2 0 1 -1
 
 3 4 0 5 -3 4 0 1
 3 4 0 5 -3 4 0 4.5
 3 4 0 5 -3 4 1 3
 3 4 0 5 -3 4 -3 3
 3 4 0 5 -3 4 0 -1
 
 -1 -1 0 3 1 -1 1 1
 -1 -1 0 3 1 -1 -2 -1
 -1 -1 0 3 1 -1 0 0
 -1 -1 0 3 1 -1 0 -1
 -1 -1 0 3 1 -1 0 -2
 
 2 0 0 2 -2 0 0 0
*/