鏈接：https://ac.nowcoder.com/acm/contest/201/L
來源：?？途W(wǎng)
?

時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 1048576K，其他語言2097152K
Special Judge, 64bit IO Format: %lld

?

題解:看樣子很復(fù)雜，其實(shí)很簡(jiǎn)單，是個(gè)最短路徑板子題，主要是存圖，這里有三種距離

一個(gè)是圓與圓之間的距離(需減去兩個(gè)圓的半徑，圓上走也不消耗體力，結(jié)果為負(fù)，距離為零)

一個(gè)是圓與直線之間的距離(需減去一個(gè)圓的半徑，結(jié)果為負(fù)，距離為0)

一個(gè)是直線與直線之間的距離(直接求就完事了)

?

另一個(gè)需要注意的是按序號(hào)代表每一個(gè)元素就行了，比如序號(hào)0代表第一根直線，1到n代表n個(gè)圓，n+1代表最后一根直線

用鄰接矩陣存距離就行辣~(數(shù)據(jù)感人，大數(shù)不能用)?

?	0	1	2	```	n	n+1
0	?	?	?	?	?	?
1	?	?	?	?	?	?
2	?	?	?	?	?	?
```	?	?	?	?	?	?
n	?	?	?	?	?	?
n+1	?	?	?	?	?	?

題目描述

Eagle Jump公司正在開發(fā)一款新的游戲。Hifumi Takimoto作為其中的員工，獲得了提前試玩的機(jī)會(huì)?，F(xiàn)在她正在試圖通過一個(gè)迷宮。
這個(gè)迷宮有一些特點(diǎn)。為了方便描述，我們對(duì)這個(gè)迷宮建立平面直角坐標(biāo)系。迷宮中有兩條平行直線 L1:Ax+By+C1=0, L2:Ax+By+C2=0，還有 n 個(gè)圓 。角色在直線上、圓上、園內(nèi)行走不消耗體力。在其他位置上由S點(diǎn)走到T點(diǎn)消耗的體力為S和T的歐幾里得距離。
Hifumi Takimoto想從 L1 出發(fā)，走到 L2 。請(qǐng)計(jì)算最少需要多少體力。

輸入描述:

第一行五個(gè)正整數(shù) n,A,B,C1,C2 (1≤ n ≤ 1000, -10000 ≤ A,B,C1,C2 ≤ 10000)，其中 A,B 不同時(shí)為 0。 接下來 n 行每行三個(gè)整數(shù) x,y,r(-10000 ≤ x,y ≤ 10000, 1≤ r ≤ 10000) 表示一個(gè)圓心為 (x,y)，半徑為 r 的圓。

輸出描述:

僅一行一個(gè)實(shí)數(shù)表示答案。與正確結(jié)果的絕對(duì)誤差或者相對(duì)誤差不超過 10-4 即算正確。

?

示例1

輸入

復(fù)制

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

輸出

復(fù)制

0.236068

最后附上代碼

#include <iostream> #include <cmath> #include <cstring> using namespace std; double n,a,b,c1,c2; const int maxn=1e3+2; #define INF 0x3f3f3f3f double map[maxn][maxn]; double d[maxn]; bool used[maxn]; int V;struct node{double x;double y;double r; }cir[maxn]; double disc(node a,node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))-a.r-b.r; } double discx(double a,double b,double c,node ci){return fabs(ci.x*a+ci.y*b+c)/sqrt(a*a+b*b)-ci.r; } void dijkstra(int s){V=n+2;fill(d,d+V,INF);fill(used,used+V,false);d[s]=0;while(true){int v=-1;for(int u=0;u<V;u++){if(!used[u] &&(v==-1||d[u]<d[v]))v=u;}if(v==-1)break;used[v]=true;for(int u=0;u<V;u++){d[u]=min(d[u],d[v]+map[v][u]);}} } int main(){cin>>n>>a>>b>>c1>>c2;for(int i=1;i<n+1;i++){cin>>cir[i].x>>cir[i].y>>cir[i].r;}memset(map,INF,sizeof(map));for(int i=1;i<n;i++){for(int j=i+1;j<n+1;j++){double temp=disc(cir[i],cir[j]);if(temp>0){map[i][j]=map[j][i]=temp;}elsemap[i][j]=map[j][i]=0;}}int p=n+1;for(int i=1;i<n+1;i++){double temp=discx(a,b,c1,cir[i]);if(temp>0){map[0][i]=map[i][0]=temp;}elsemap[0][i]=map[i][0]=0;double tmp=discx(a,b,c2,cir[i]);if(tmp>0){map[p][i]=map[i][p]=tmp;}elsemap[p][i]=map[i][p]=0;}map[0][p]=map[p][0]=(fabs(c1-c2)/sqrt(a*a+b*b));dijkstra(0);cout<<d[p]<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/UUUUh/p/10284065.html

總結(jié)

以上是生活随笔為你收集整理的(花里胡哨)New Game!(牛客国庆集训派对Day1)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。