UVa01001 Say Cheese

---

題目連結

---

• ❗️ 題意
  在一塊起司中，給有n個球形的洞，在洞裡的移動不耗時間，再給定出發點與終點，問你從出發點到終點，的最短路徑(距離：時間 = 1:10)是多少?

---

• ✔️ 題解
  將起點與終點的半徑設為0(變成半徑為0的球)，再將所有球的考慮過半徑的距離算出來，做一次Floyd Warshall就可找出起點到終點的最短路徑(時間)。
  假設有點A與點B，A(x)代表A的座標在x，r則是其半徑，我們可以分成以下三個case來討論：
  | Case1:兩圓外離 | Case2:兩圓外切 | Case3:兩圓相交 |

:————————-:|:————————-:|:————————-:
| |

因此，我們可以導出以下式子
$$
distance(a, b) =
\begin{cases}
\overline{AB} - r_{a} - r_{b}, & \text{if $\overline{AB}$ > $r_{a}$ + $r_{b}$} \\
0, & \text{if $\overline{AB}$ $\le$ $r_{a}$ + $r_{b}$}
\end{cases}
$$
建完圖後這題就變成單純的最短路啦，我們只要利用floyd warshall或任何求最短路的演算法，找出起點與終點的距離再乘以10就是答案了。

• 💻 程式碼

  10ms

  #include <bits/stdc++.h>
  using namespace std;
  
  double dis_cal(int x1, int y1, int z1, int x2, int y2, int z2){
  	double x = x1 - x2, y = y1 - y2, z = z1 - z2;
  	return sqrt(x * x + y * y + z * z);
  }
  
  struct holes{
  	int x, y, z, r;
  };
  
  holes arr[105];
  double dis[105][105];
  
  int main(){
  	int n;
  	int kase = 0;
  	while(cin >> n && n != -1){
  		for(int i = 1; i <= n; i++){
  			cin >> arr[i].x >> arr[i].y >> arr[i].z >> arr[i].r;
  		}
  		// 起點與終點可以視為半徑=0的洞
  		cin >> arr[0].x >> arr[0].y >> arr[0].z;
  		arr[0].r = 0;
  		cin >> arr[n + 1].x >> arr[n + 1].y >> arr[n + 1].z;
  		arr[n + 1].r = 0;
  		for(int i = 0; i < n + 2; i++){
  			for(int j = 0; j < n + 2; j++){
  				dis[i][j] = INT_MAX;
  			}
  		}
  		// 利用公式，紀錄任兩點的距離。
  		for(int i = 0; i < n + 2; i++){
  			for(int j = 0; j < n + 2; j++){
  				double d = dis_cal(arr[i].x, arr[i].y, arr[i].z, arr[j].x, arr[j].y, arr[j].z);
  				if(d <= arr[i].r + arr[j].r)
  					dis[i][j] = 0;
  				else{
  					dis[i][j] = d - arr[i].r - arr[j].r;
  				}
  
  			}
  		}
  		// floyd warshall
  		for(int k = 0; k < n + 2; k++){
  			for(int i = 0; i < n + 2; i++){
  				for(int j = 0; j < n + 2; j++){
  					dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  				}
  			}
  		}
  		printf("Cheese %d: Travel time = %d sec\n", ++kase, (int)round(dis[0][n + 1] * 10));
  	}
  }

  答案記得乘以10後做round，否則會有精度問題QQ

---

• 🧠 心得
  記得這是某次我們學校自辦賽的題目，當初做完這題的時候一直WA，找不到自己哪裡寫錯了，想說是哪裡想法有錯，最後被精度搞了一波🥲。
  賽後發現自己的想法是正確的，只差在取round的部分，就想在這邊分享給大家啦～

---