fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long int ll;
  3. #define ld long double
  4. #define maxx 100000000000.01
  5. #define INF 100000000000.01
  6. #define rep(i,n) for (i = 0; i < n; ++i) 
  7. #define pb push_back
  8. #define vp vector< pair<int,int> >
  9. #define pr pair<int,int>
  10. typedef long long int ll;
  11. typedef unsigned long long int ull;
  12. using namespace std;
  13.  
  14. ld distance(ll x1,ll y1,ll x2,ll y2)
  15. {
  16. 	ld ans;
  17. 	ans = sqrt( pow(x1-x2,2) + pow(y1-y2,2) );
  18. 	return ans;
  19. }
  20.  
  21. int main()
  22. {
  23. 	int t,n,m,k,i,j;
  24. 	ll x,y;
  25. 	ld temp;
  26. 	pr start;
  27. 	cin >> t;
  28. 	while(t--)
  29. 	{
  30. 		int hh = 5010;
  31. 		cin >> x >> y;
  32. 		start.first = x;
  33. 		start.second = y;
  34.  
  35. 		cin >> n >> m >> k;
  36. 		vp arr(n);vp brr(m); vp crr(k); 
  37. 		vector<ld> SAB; vector<ld> SCD;vector<ld> vrr1(hh); vector<ld> vrr2(hh);  
  38. 		ld min1=maxx,min2=maxx,ans=INF;
  39. 		rep(i,n)
  40. 		{
  41. 			cin >> arr[i].first >> arr[i].second;
  42. 			temp = distance(arr[i].first,arr[i].second,start.first,start.second);
  43. 			SAB.push_back(temp);
  44. 		}
  45. 		rep(i,m)
  46. 		{
  47. 			cin >> brr[i].first >> brr[i].second;
  48. 			temp = distance(brr[i].first,brr[i].second,start.first,start.second);
  49. 			SCD.push_back(temp);
  50.  
  51. 		}
  52. 		rep(i,k)
  53. 		{
  54. 			cin >> crr[i].first >> crr[i].second;
  55. 		}
  56. 		/*
  57. 		rep(i,n)
  58. 			cout << arr[i].first << " "<< arr[i].second << "\n";
  59. 		cout << "END\n";
  60. 		*/
  61. 		rep(i,m)
  62. 		{ 
  63. 			// Already calculated (x,y) --> (brr[i].F,brr[i].S)
  64. 			vrr2[i] = maxx;
  65. 			rep(j,k)
  66. 			{
  67. 				vrr2[i] = min(vrr2[i],distance(brr[i].first,brr[i].second,crr[j].first,crr[j].second) );
  68. 			}
  69. 		}
  70.  
  71. 		rep(i,n)
  72. 		{
  73. 			// Already calculated (x,y) --> (arr[i].F,arr[i].S)
  74. 			vrr1[i] = maxx;
  75. 			rep(j,k)
  76. 			{
  77. 				vrr1[i] = min(vrr1[i],distance(arr[i].first,arr[i].second,crr[j].first,crr[j].second) );
  78. 			}
  79. 		}
  80.  
  81. 		rep(i,n)
  82. 		{
  83. 			rep(j,m)
  84. 			ans = min(	min(ans,SAB[i]+distance(arr[i].first,arr[i].second,brr[j].first,brr[j].second)+vrr2[j]),
  85. 						SCD[j]+distance(arr[i].first,arr[i].second,brr[j].first,brr[j].second)+vrr1[i] );
  86. 		}
  87. 		cout << setprecision(12) << ans << "\n";
  88.  
  89.  
  90. 	}
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 4444KB
comments (?)
stdin
copy 
2
1 4
3 2 2
4 4 2 0 8 1
10 1 3 1
1 3 9 5
6 4
2 2 3
7 10 5 7
1 6 2 3
1 8 0 7 0 2
stdout
copy 
8.18204249801
8.69959684816
https://ideone.com/m0q8B1
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!