隐藏
「bsoj3795」圆 - 计算几何+路径规划 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bsoj3795」圆 - 计算几何+路径规划

题目大意

平面上有n个圆,给定起点和终点,你只能在圆内及圆周上行走,问从起点到终点的最短路程。


题目分析

根据路径规划问题的套路,我们需要把不定的路径转化为定的路径。
考虑哪些路径是一定不会被用到的。

这样的路径一定不会用到,为什么,因为我们把拐点移动到圆的交点处长度一定会变小。

因此我们只需要将圆的交点与$s$、$t$两两连边求最短路即可。

思路很简单,实现相当复杂,因为我们要实现以下两个操作:

  • 求圆的交点
  • 求线段是否被圆完全覆盖:(不在圆内的边不合法)

又一道调试题


求圆的交点

根据mathematica软件联立圆方程得:

哇好大一坨式子,我们化简一下:

哇怎么还是这么大一坨式子?
相对于刚刚已经够少了吧,并且比人算好多了,老老实实敲代码吧。


判断线段被圆完全覆盖

首先计算直线方程:$y=kx+b$
若直线垂直于$x$轴特判一下。
根据mathematica联立圆与直线方程得:

哇好短一坨式子,敲代码吧。

对于垂直于$x$轴的直线我们只关心其$y$的值,对于其余的直线我们只关心其$x$的值。
那么这就转化为了一个线段覆盖问题。

如果线段被圆完全覆盖,那么在到达终点前,累加和一定是$>0$的,否则说明线段不被圆完全覆盖。


代码

然后就开始愉快的敲代码吧。

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const double eps=1e-6;
struct Point {
double x,y;
Point(double _x=0,double _y=0):x(_x),y(_y) {}
} p[1005];
struct Circle {
Point a;
double r;
} c[35];
double sqr(double x) {
return x*x;
}
int n,cnt=2;
double Dist(Point a,Point b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void Circle_Intersection(Circle x,Circle y) {
double dist=Dist(x.a,y.a);
if(x.r+y.r<dist||abs(x.r-y.r)>dist)return; //不相交
double tmp=sqr(y.a.x)-sqr(x.a.x)+sqr(y.a.y)-sqr(x.a.y)+sqr(x.r)-sqr(y.r);
Point p1,p2;
if(x.a.y==y.a.y) { //连线垂直y轴
p1.x=p2.x=tmp/2/(y.a.x-x.a.x);
double tmp2=sqr(x.r)-sqr(p1.x-x.a.x);
p1.y=sqrt(tmp2)+x.a.y;
p2.y=-sqrt(tmp2)+x.a.y;
} else { //来自mathematica
p1.x=(sqr(y.r)*(x.a.x-y.a.x)-sqr(x.r)*(x.a.x-y.a.x)+(x.a.x+y.a.x)*(sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))-sqrt(-(sqr(x.r-y.r)-sqr(x.a.x-y.a.x)-sqr(x.a.y-y.a.y))*(sqr(x.r+y.r)-sqr(x.a.x-y.a.x)-sqr(x.a.y-y.a.y))*sqr(x.a.y-y.a.y)))/(2*(sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y)));
p2.x=(sqr(y.r)*(x.a.x-y.a.x)-sqr(x.r)*(x.a.x-y.a.x)+(x.a.x+y.a.x)*(sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))+sqrt(-(sqr(x.r-y.r)-sqr(x.a.x-y.a.x)-sqr(x.a.y-y.a.y))*(sqr(x.r+y.r)-sqr(x.a.x-y.a.x)-sqr(x.a.y-y.a.y))*sqr(x.a.y-y.a.y)))/(2*(sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y)));
p1.y=(-sqr(x.r)*sqr(x.a.y-y.a.y)+x.a.x*sqrt(-(sqr(sqr(x.r))+sqr(-sqr(y.r)+sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))-2*sqr(x.r)*(sqr(y.r)+sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y)))*sqr(x.a.y-y.a.y))-y.a.x*sqrt(-(sqr(sqr(x.r))+sqr(-sqr(y.r)+sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))-2*sqr(x.r)*(sqr(y.r)+sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y)))*sqr(x.a.y-y.a.y))+(x.a.y-y.a.y)*(sqr(y.r)*(x.a.y-y.a.y)+(sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))*(x.a.y+y.a.y)))/(2*(sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))*(x.a.y-y.a.y));
p2.y=(-sqr(x.r)*sqr(x.a.y-y.a.y)-x.a.x*sqrt(-(sqr(sqr(x.r))+sqr(-sqr(y.r)+sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))-2*sqr(x.r)*(sqr(y.r)+sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y)))*sqr(x.a.y-y.a.y))+y.a.x*sqrt(-(sqr(sqr(x.r))+sqr(-sqr(y.r)+sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))-2*sqr(x.r)*(sqr(y.r)+sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y)))*sqr(x.a.y-y.a.y))+(x.a.y-y.a.y)*(sqr(y.r)*(x.a.y-y.a.y)+(sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))*(x.a.y+y.a.y)))/(2*(sqr(x.a.x-y.a.x)+sqr(x.a.y-y.a.y))*(x.a.y-y.a.y));
}
p[++cnt]=p1;
p[++cnt]=p2;
}
struct node {
double x,v;
bool operator < (const node& b) const {
if(fabs(x-b.x)>eps)return x<b.x;
return v>b.v;
}
} tmp[5005];
bool inCircle(Point a,Point b) {
int cnt=0;
for(int i=1; i<=n; i++) {
double int1,int2; //直线与圆的交点
if(a.x==b.x) {
double Delta=sqr(c[i].r)-sqr(a.x-c[i].a.x);
if(Delta<0)continue; //不相交
int1=c[i].a.y-sqrt(Delta);
int2=c[i].a.y+sqrt(Delta);
if(int1>int2)swap(int1,int2);
if(int1>max(a.y,b.y)&&abs(int1-max(a.y,b.y))>eps)continue;
if(int2<min(a.y,b.y)&&abs(int2-min(a.y,b.y))>eps)continue;
if(int1<min(a.y,b.y))int1=min(a.y,b.y);
if(int2>max(a.y,b.y))int2=max(a.y,b.y);
} else {
double k=(a.y-b.y)/(a.x-b.x),_b=a.y-k*a.x;
double Delta=-sqr(_b)+sqr(c[i].r)+sqr(k)*sqr(c[i].r)-2*_b*k*c[i].a.x-sqr(k)*sqr(c[i].a.x)+2*_b*c[i].a.y+2*k*c[i].a.x*c[i].a.y-sqr(c[i].a.y);
if(Delta<0)continue; //不相交
int1=(-k*_b+c[i].a.x+k*c[i].a.y-sqrt(Delta))/(1+sqr(k));
int2=(-k*_b+c[i].a.x+k*c[i].a.y+sqrt(Delta))/(1+sqr(k));
if(int1>int2)swap(int1,int2);
if(int1>max(a.x,b.x)&&abs(int1-max(a.x,b.x))>eps)continue;
if(int2<min(a.x,b.x)&&abs(int2-min(a.x,b.x))>eps)continue;
if(int1<min(a.x,b.x))int1=min(a.x,b.x);
if(int2>max(a.x,b.x))int2=max(a.x,b.x);
}
tmp[++cnt]=(node) {int1,1};
tmp[++cnt]=(node) {int2,-1};
}
if(cnt==0)return false;
sort(tmp+1,tmp+cnt+1);
int sum=0;
for(int i=1; i<cnt; i++) {
sum+=tmp[i].v;
if(sum<=0)return false;
}
return true;
}
struct Edge {
int from,to;
double dist;
};
vector<Edge>edges[5005];
void AddEdge(int x,int y,double v) {
edges[x].push_back((Edge) {
x,y,v
});
}
struct QueNode {
double d;
int u;
bool operator < (const QueNode& b) const {
return d>b.d;
}
};
double dist[5005];
bool vst[5005];
void Dijkstra(int s) {
memset(dist,0x7f,sizeof(dist));
priority_queue<QueNode>Q;
dist[s]=0;
Q.push((QueNode) {
dist[s],s
});
while(!Q.empty()) {
int Now=Q.top().u;
Q.pop();
if(vst[Now])continue;
vst[Now]=1;
for(auto &e:edges[Now]) {
int Next=e.to;
if(dist[Next]>dist[Now]+e.dist) {
dist[Next]=dist[Now]+e.dist;
Q.push((QueNode) {
dist[Next],Next
});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1; i<=n; i++)cin>>c[i].a.x>>c[i].a.y>>c[i].r;
cin>>p[1].x>>p[1].y>>p[2].x>>p[2].y;
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
Circle_Intersection(c[i],c[j]);
for(int i=1; i<cnt; i++)
for(int j=i+1; j<=cnt; j++)
if(inCircle(p[i],p[j])) {
double dist=Dist(p[i],p[j]);
AddEdge(i,j,dist);
AddEdge(j,i,dist);
}
Dijkstra(1);
printf("%0.4lf\n",dist[2]);
return 0;
}

姥爷们赏瓶冰阔落吧~