ccbeginner

UVa Q534

Jan 26th, 2020
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q534
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct stat{
  6.     int idx;
  7.     double dist;
  8.     bool operator>(const stat x)const{return dist > x.dist;}
  9.     bool operator<(const stat x)const{return dist < x.dist;}
  10. };
  11.  
  12. struct pt{
  13.     int x,y;
  14. }arr[200];
  15. bool vis[200];
  16.  
  17. double calc(pt a, pt b){
  18.     return sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y));
  19. }
  20.  
  21. int32_t main(){
  22.     int n, cnt = 0;
  23.     while(cin >> n){
  24.         if(n == 0)break;
  25.         for(int i = 0; i < n; ++i)cin >> arr[i].x >> arr[i].y;
  26.         memset(vis, 0, sizeof(vis));
  27.         priority_queue<stat, deque<stat>, greater<stat>> pq;
  28.         stat tmd = {.idx = 0, .dist = 0};
  29.         pq.push(tmd);
  30.         double ans;
  31.         while(!pq.empty()){
  32.             tmd = pq.top();
  33.             pq.pop();
  34.             vis[tmd.idx] = 1;
  35.             if(tmd.idx == 1){
  36.                 ans = tmd.dist;
  37.                 break;
  38.             }
  39.             for(int i = 0; i < n; ++i){
  40.                 if(!vis[i]){
  41.                     stat nxt = {.idx = i, .dist = max(tmd.dist, calc(arr[tmd.idx], arr[i]))};
  42.                     pq.push(nxt);
  43.                 }
  44.             }
  45.         }
  46.         cout << "Scenario #" << ++cnt << endl;
  47.         printf("Frog Distance = %.3f\n\n", ans);
  48.     }
  49.     return 0 ;
  50. }
RAW Paste Data