Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.74 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <climits>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. double find_dist(int x1, int y1, int x2, int y2)
  9. {
  10. return(sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)));
  11.  
  12. }
  13.  
  14. int main()
  15. {
  16. int n, m;
  17. double d;
  18. cin >> n;
  19. double dist[n+1][n+1];
  20.  
  21. for(int i = 0; i < n; i++)
  22. {
  23. for(int j = 0; j < n; j++)
  24. {
  25. dist[i][j] = INT_MAX-1;
  26. }
  27. dist[i][i] = 0;
  28. }
  29.  
  30. int t1, t2, tw;
  31. vector< pair<int, int> > adj(n);
  32. for(int i = 0; i < n; i++)
  33. {
  34. cin >> t1 >> t2;
  35. adj[i].first = t1;
  36. adj[i].second = t2;
  37. }
  38.  
  39. for(int i = 0; i < n-1; i++)
  40. {
  41. for(int j = i+1; j < n; j++)
  42. {
  43. //double d = abs(adj[i].first - adj[j].first) + abs(adj[i].second - adj[j].second);
  44. double dt = find_dist(adj[i].first, adj[i].second, adj[j].first, adj[j].second);
  45. //cout << dt << endl;
  46. if(dt <= 10.0)
  47. dist[i][j] = dist[j][i] = dt;
  48. }
  49. }
  50.  
  51. for(int k = 0; k < n; k++)
  52. {
  53. for(int i = 0; i < n; i++)
  54. {
  55. for(int j = 0; j < n; j++)
  56. {
  57. d = dist[i][k] + dist[k][j];
  58. if(d < dist[i][j])
  59. {
  60. dist[i][j] = d;
  61. }
  62. }
  63. }
  64. }
  65.  
  66. int rez = -1;
  67. for(int i = 0; i < n; i++)
  68. {
  69. for(int j = 0; j < n; j++)
  70. {
  71. //cout << dist[i][j] << " ";
  72. if(dist[i][j] > rez)
  73. rez = dist[i][j];
  74.  
  75. }
  76. // cout << endl;
  77. }
  78.  
  79. if(rez == INT_MAX-1)
  80. cout << "NE"<< endl;
  81. else
  82. cout << rez << endl;
  83. return(0);
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement