Advertisement
Guest User

Untitled

a guest
Jul 1st, 2015
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.56 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <iomanip>
  7. #include <queue>
  8.  
  9. #define INF 0x3f3f3f3f
  10.  
  11. using namespace std;
  12.  
  13. struct point{
  14. int x, y;
  15.  
  16. point(int a, int b){
  17. x = a, y = b;
  18. }
  19.  
  20. bool equals(point a){
  21. return x == a.x && y == a.y;
  22. }
  23.  
  24. double dist(point a){
  25. return sqrt(pow((double)(x - a.x), 2) +
  26. pow((double)(y - a.y), 2));
  27. }
  28. };
  29.  
  30. int nodeCount;
  31. bool visited[201];
  32. double dist[201], matrix[201][201], maxDistance;
  33. vector<point> p;
  34. queue<int> dijkstra;
  35.  
  36. void init(){
  37. p.clear();
  38. while (!dijkstra.empty()) dijkstra.pop();
  39. maxDistance = -1;
  40.  
  41. for (int i = 0; i < nodeCount; i++){
  42. visited[i] = false;
  43. dist[i] = INF;
  44. }
  45. }
  46.  
  47. double dmax(double a, double b){
  48. return (a > b ? a : b);
  49. }
  50.  
  51. double dmin(double a, double b){
  52. return (a < b ? a : b);
  53. }
  54.  
  55. int main(){
  56. int kCount = 1;
  57.  
  58. while (true){
  59. cin >> nodeCount;
  60. if (nodeCount == 0) break;
  61.  
  62. init();
  63.  
  64. for (int i = 0, x, y; i < nodeCount; i++){
  65. cin >> x >> y;
  66. p.push_back(point(x, y));
  67. }
  68.  
  69. for (int i = 0; i < nodeCount; i++)
  70. for (int j = 0; j < nodeCount; j++)
  71. matrix[i][j] = p[i].dist(p[j]);
  72.  
  73. for (int k = 0; k < nodeCount; k++)
  74. for (int i = 0; i < nodeCount; i++)
  75. for (int j = 0; j < nodeCount; j++)
  76. matrix[i][j] = dmin(matrix[i][j], dmax(matrix[i][k], matrix[k][j]));
  77.  
  78. cout << "Scenario #" << kCount << endl;
  79. cout << "Frog Distance = " << fixed << setprecision(3) << matrix[0][1] << endl;
  80. cout << endl;
  81.  
  82. kCount++;
  83.  
  84. }
  85.  
  86. system("pause");
  87. return 0;
  88.  
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement